Binary vs Decimal

Time limit1sMemory limit256 MB

Summary

Find the n-th positive integer whose decimal digits form a suffix of its binary representation.

Level: Medium7 of 10
Topics: Number theory, Bit manipulation, Brute force
Solved: No attempts yet

Problem

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

For example, $10_{10} = 1010_2$ , and the decimal representation 10 matches the last two digits of the binary representation 1010, so 10 is bindecimal. On the other hand $1010_{10} = 1111110010_2$ , and 1010 is not a suffix of 1111110010, so 1010 is not bindecimal. Neither is 42, because $42_{10} = 101010_2$ and 42 is not a suffix of 101010.

Find the $n$ -th smallest bindecimal number.

Input

The first and only line contains one integer $n$ . ( $1 \le n \le 10000$ )

Output

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

Hint

A binary representation uses only the digits 0 and 1, so the decimal representation of a bindecimal number also uses only 0 and 1. Here are the smallest numbers whose decimal representation contains only 0's and 1's.

Decimal	Binary	Comment
1	1	1st bindecimal number
10	1010	2nd bindecimal number
11	1011	3rd bindecimal number
100	1100100	4th bindecimal number
101	1100101	5th bindecimal number
110	1101110	6th bindecimal number
111	1101111	7th bindecimal number
1000	1111101000	8th bindecimal number
1001	1111101001	9th bindecimal number
1010	1111110010	Not a bindecimal number
1011	1111110011	Not a bindecimal number
1100	10001001100	10th bindecimal number

Examples3

Example 1
Input
```
1
```
Expected output
```
1
```
Example 2
Input
```
2
```
Expected output
```
10
```
Example 3
Input
```
10
```
Expected output
```
1100
```