Numerical sequence#552

Numerical sequence

1 second

64 megabytes

Easy

Dmytro recently started working at the Scientific Research Institute "Number Sequences". As the name suggests, the institute's main activity is conducting various studies in the area of numerical sequences. Recently, the head of the department where Dmytro started working encountered a very interesting sequence of numbers $a_{1}, a_{2}, \dots$ a_1, a_2, \dots, defined as follows: the first term $a_{1} = 0$ a_1 = 0, and each subsequent number $a_{i}$ a_i ( $i > 1$ i > 1) is defined as the smallest natural number greater than $a_{i - 1}$ a_{i-1}, whose decimal representation does not contain any digits present in the decimal representation of $a_{i - 1}$ a_{i-1}.

You are required to write a program that, given the value of $n$ , computes the value of $a_{n}$ a_n.

Input

One integer $n$ ( $1 \leq n \leq 500$ 1 \leq n \leq 500).

Output

Print a single number $a_{n}$ a_n.

Examples

Example 1

Loading

a_{1}, a_{2}, \dots

a_{1} = 0

a_{i}

i > 1

a_{i - 1}

a_{i - 1}

a_{n}

1 \leq n \leq 500

a_{n}