You would like to write a list of positive integers 1,2,3,\ldots using your computer. However, you can press each key 0–9 at most n times during the process.

What is the last number you can write?

Input

The only input line contains the value of n.

Output

Print the last number you can write.

Constraints

• 1 \le n \le 10^{18}

Example

Input:

5

Output:

12

Explanation: You can write the numbers 1,2,\ldots,12. This requires that you press key 1 five times, so you cannot write the number 13.