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 = 10101010 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.
输入描述:
The first and the only line contains one integer — n (1 ≤ n ≤ 10 000).
输出描述:
Print one integer — the n-th smallest bindecimal number in decimal notation.
示例3
说明
Here is a table with the first few numbers which contain only 0’s and 1’s in their decimal representation (it is clear that all other numbers are not bindecimal):
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