# Binary vs Decimal

# Binary vs Decimal

Bruce has recently got a job at NEERC (Numeric Expression Engineering & Research Center) facility, which studies and produces many kinds of curious numbers. His first assignment is to perform a study of bindecimal numbers.

A positive integer is called bindecimal if its decimal representation is a suffix of its binary representation; both binary and decimal representations are considered without leading zeros. For example, `10`

= _{10}`1010`

, thus _{2}**10** is a bindecimal number. The numbers `1010`

= _{10}`1111110010`

and _{2}`42`

= _{10}`101010`

are, evidently, not bindecimal._{2}

First of all, Bruce is going to create a list of bindecimal numbers. Help him find the **n**-th smallest bindecimal number.

#### Input

The first and the only line contains one integer **n** (**1** ≤ **n** ≤ **10 000**).

#### Output

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

1

1

2

10

10

1100