백십일 크로나

지폐 생산을 담당하는 Tumba 제지 공장에서 인쇄기가 고장 났다. 이제 이 인쇄기는 숫자 ”1”만 인쇄할 수 있다. 새 인쇄기를 구입하는 데는 스웨덴 화폐로 $N$크로나가 들지만, 안타깝게도 제지 공장은 돈이 완전히 바닥났다. 하지만 제지 공장에서 직접 지폐를 인쇄하므로, 새 기계를 살 수 있도록 새 돈을 인쇄하면 되지 않을까?

고장 난 인쇄기는 숫자 ”1”만 인쇄할 수 있으므로, 액면가가 $1$크로나, $11$크로나, $111$크로나, $1111$크로나 등인 지폐만 인쇄할 수 있다.

이제 제지 공장은 새 인쇄기의 값을 치르기 위해 지폐를 몇 장 인쇄해야 하는지 궁금해한다. 필요한 것보다 많은 돈을 인쇄하는 것은 부도덕하므로 정확한 금액, 즉 정확히 $N$크로나를 지불할 수 있어야 하며, 따라서 가능한 한 적은 수의 지폐를 인쇄하려 한다. 제지 공장에서 인쇄해야 하는 지폐의 수를 계산하는 프로그램을 작성하라.

배점

제출한 해답은 여러 테스트 케이스 그룹으로 나누어 채점된다. 한 그룹의 점수를 얻으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 배점 | 제한

$1$ |$20$| $N \leq 1000$

$2$ |$40$| $N \leq 10^6$

$3$ |$40$| 추가 제한이 없다.

처음이자 유일한 줄에 새 인쇄기의 가격을 크로나 단위로 나타내는 정수 $N$ ($1 \leq N \leq 10^9$)가 주어진다.

인쇄해야 하는 지폐의 최소 장수를 나타내는 정수를 출력한다.

• 첫 번째 예제에서는 $1$크로나 지폐 한 장과 $11$크로나 지폐 두 장을 사용할 수 있다.

• 두 번째 예제에서는 $1$크로나, $11$크로나, $111$크로나, $1111$크로나, $11111$크로나 지폐를 각각 한 장씩 사용할 수 있다.