## LQDNUMS - LQDNUMBERS

During a meeting with professors in the Asian Confederation of Mathematics, a Russian professor came up with a problem:

He choose a number N (1 ≤ N ≤ 10^18), then write all the numbers from 1 to N to form a continuous string of digits. Next he replaced substrings of identical digits with a single digit. For example string fragment "14445556677666" would be changed to "145676". Then he asked his fellow professors: given a length of string S determine the number N which results in that kind of string S. Can you help the professors?

### Input

A single number M, length of the string S (1 ≤ M ≤ 1018.)

### Output

A single number N, the number which Russian professor selected.

### Example

```Input:
13

Output:
12```

### Explanation:

With N = 12, we get the string: 123456789101112.

Because there are three consecutive number ones, we delete the first two numbers, then we have: 1234567891012. The length of this string is 13

 Được gửi lên bởi: Tmbao Ngày: 2011-05-29 Thời gian chạy: 1s Giới hạn mã nguồn: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Ngôn ngữ cho phép: Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED Nguồn bài: Ukraina OI