Problems
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 \textbf{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_2$, thus $10$ is a bindecimal number. The numbers $1010_{10} = 1111110010_2$ and $42_{10} = 101010_2$ 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.
\InputFile
The first and the only line contains one integer $n~(1 \le n \le 10^4)$.
\OutputFile
Print one integer --- the $n$-th smallest bindecimal number in decimal notation.
Input example #1
1
Output example #1
1
Input example #2
2
Output example #2
10
Input example #3
10
Output example #3
1100