So far the country of Byteland has identified its citizens with bit strings of length 10, for example 0001011010 or 1010001110. However now they have to change the identification system due to running out of different bit strings.

In the new system each citizen is identified with a string of length 10, consisting of digits from 0 to 9. Additionally the king of Byteland has ruled that ID strings of any two citizens should differ in more than one position. For example it is illegal to have ID 0000000011 and ID 0000030011.

The new ID strings are issued to citizens in lexicographical order. The first citizen gets the ID 0000000000, and the following citizens get the first ID that does not break the law. (The second citizen gets the id 0000000011).

Given number n, determine what is the ID of the nth citizen.

Input

The input contains one integer, n.

Output

Output the ID of the nth citizen.

Constraints

• 1 \le n \le 1024

Examples

Input:

1

Output:

0000000000

Input:

3

Output:

0000000022

Input:

22

Output:

0000000213