근우의 다이어리 꾸미기

곧 2018년이 끝나고 2019년이 온다.

근우는 2019년에는 꼭 다이어리를 쓰기로 했다. 그런데 처음 써보는 다이어리에 쓸 내용이 없어 고민하던 중, 자신의 목표 연봉을 다이어리 맨 앞에 쓰기로 했다.

다이어리를 쓰는 사람은 알겠지만 예쁜 다이어리의 핵심은 스티커다. 그래서 근우는 목표 연봉을 손으로 쓰지 않고 스티커로 붙이려고 한다. 목표 연봉이 100이라면 [1] [0] [0]과 같이 붙이는 것이다. [1]이란 1이 써진 스티커이고, 다른 숫자도 같은 규칙을 따른다.

근우는 자신의 연봉 최댓값이 N임을 안다. 그래서 0부터 N까지의 수를 스티커로 하나씩 모두 표현하려고 한다. 최댓값 N이 10이면 만드는 과정은 다음과 같다.

• 스티커 더미에서 [0] 하나를 가져와 0을 표현한다 ([0]). 이후 사용한 스티커 [0]을 스티커 더미로 되돌린다.
• 스티커 더미에서 [1] 하나를 가져와 1을 표현한다 ([1]). 이후 사용한 스티커 [1]을 스티커 더미로 되돌린다.
• 9까지도 같은 방법으로 표현한다.
• 스티커 더미에서 [0] 하나와 [1] 하나를 가져와 10을 표현한다 ([1][0]). 이후 사용한 스티커 [0]과 [1]을 스티커 더미로 되돌린다.

따라서 N = 10이면 스티커가 [0]부터 [9]까지 하나씩만 있으면 모두 표현할 수 있다.

필요한 스티커를 사러 고려대 하나스퀘어 유니스토어에 도착한 근우는 고민이 생겼다. 스티커 팩에는 [0]부터 [9]까지 스티커가 한 장씩밖에 없는데, 생각보다 너무 비싼 것이다.

그래서 근우는 0부터 N까지 모든 수를 하나씩 표현할 수 있도록 최소한의 스티커 팩만 사려고 한다.

근우는 매우 똑똑하지만, 스티커 팩 가격에 충격을 받아 계산할 수 없는 상태가 돼버렸다.

여러분이 근우의 최대 목표액 N이 주어졌을 때, 근우에게 필요한 최소 스티커 팩의 개수를 구해주자.

첫 번째 줄에 근우의 연봉 최댓값을 나타내는 정수 N이 주어진다. (0 ≤ N ≤ 1,000,000,000)

첫 번째 줄에 근우가 0부터 N까지 스티커로 표현하기 위해 사야 하는 스티커 팩의 최소 개수를 출력한다.