Binary vs Decimal#7562

Binary vs Decimal

1 second

128 megabytes

Medium

Bruce has recently started working at the NEERC (Numeric Expression Engineering Research Center) facility, which studies and produces many kinds of curious numbers. His first assignment is to study bindecimal numbers.

A positive integer is called bindecimal if its decimal representation is a suffix of its binary representation. Both representations are considered without leading zeros.

For example, $1 0_{10} = 101 0_{2}$ 10_{10} = 1010_2, so $10$ is a bindecimal number. The numbers $101 0_{10} = 111111001 0_{2}$ 1010_{10} = 1111110010_2 and $4 2_{10} = 10101 0_{2}$ 42_{10} = 101010_2 are not bindecimal numbers.

As his first task, Bruce is going to create a list of bindecimal numbers. Help him find the $n$ -th smallest bindecimal number.

Input

One integer $n (1 \leq n \leq 1 0^{4})$ n~(1 \le n \le 10^4).

Output

Print one integer — the $n$ -th smallest bindecimal number in decimal notation.

Examples

Example 1

Loading

Example 2

Loading

Example 3

Loading

1 0_{10} = 101 0_{2}

101 0_{10} = 111111001 0_{2}

4 2_{10} = 10101 0_{2}

n (1 \leq n \leq 1 0^{4})