Numerical sequence

Dima has recently joined the Scientific Research Institute "Number Sequences". As the name of this institution, the main focus of his work is to conduct various researches in the field of numerical sequences. Recently the head of the department, where he began work Dima, in addressing one of the problems encountered with a very interesting sequence of numbers a_1, a_2, …, which is defined as follows: the first term a_1 = 0, and each subsequent number a_i (i > 1) is defined as the smallest natural number greater than a_{i-}_1, decimal record does not contain figures presented in decimal notation a_{i-}_1.

Need to write a program, which calculates the value of n the value of a_n.

Input

One integer n (1 ≤ n ≤ 500).

Output

Print a single number a_n.

Examples