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$.