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, 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 (1 ≤ n ≤ 10 000).
Output
Print one integer - the n-th smallest bindecimal number in decimal notation.
1
1
2
10
10
1100