Smooth numbers

A number is considered smooth if its digits, starting from the most significant, form a non-decreasing sequence. We will list all such numbers in ascending order and assign each a position. Your task is to determine and output the n-th smooth number for a given n.

Input

A single integer n (1 ≤ n ≤ 2147483647).

Output

Print the smooth number that corresponds to the position n.

Examples