Exile_2k4 có số nguyên dương ~N~. Cậu sẽ chơi một trò chơi nhỏ với con số này.

Đầu tiên, cậu sẽ viết tất cả các số từ ~1~ đến ~N~ thành một xâu liên tiếp ~S_N = 12345678910111213 \dots~ Sau đó, cậu sẽ nén các xâu con có các chữ số giống nhau của xâu ~S~ này thành về ~1~ chữ số duy nhất.

Lấy ví dụ về việc nén xâu con, với ~N = 12~ ta có xâu ~S_{12} = 123456789101112~ thì sau khi nén, ta có ~S_{12} = 1234567891012~ có độ dài là ~M = 13~. Như vậy, ta dễ thấy là ~2~ chữ số liên tiếp nhau của ~S~ sau khi nén luôn khác nhau.

Bây giờ Exile_2k4 đố bạn một câu hỏi ngược. Cậu ta sẽ cho bạn số ~M~, và nhiệm vụ của bạn là tìm số ~K~ lớn nhất sao cho độ dài của xâu ~S_K~ sau khi nén không vượt quá ~M~.

Dễ chứng minh được là độ dài của xâu ~S_K~ sau khi nén là duy nhất với mỗi ~K~.

Bạn có thể làm được không?

Input

Số nguyên dương ~M \leq 10^{18}~, độ dài của xâu ~S~ sau khi nén.

Output

Số ~K~ lớn nhất là đáp án của câu hỏi trên.

Sample Input 1

13

Sample Output 1

12

Sample Input 2

5

Sample Output 2

5

Sample Input 3

69

Sample Output 3

42