 Problems

# 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, `1010` = `10102`, thus 10 is a bindecimal number. The numbers `101010` = `11111100102` and `4210` = `1010102` are, evidently, not bindecimal.

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 (1n10 000).

#### Output

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

Time limit 1 second
Memory limit 128 MiB
Input example #1
```1
```
Output example #1
```1
```
Input example #2
```2
```
Output example #2
```10
```
Input example #3
```10
```
Output example #3
```1100
```
Source 2015 ACM NEERC, Semifinals, December 6, Problem B