|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|1 초||256 MB||76||40||24||50.000%|
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.
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):
|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|