11736번 - 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, 10₁₀ = 1010₂, thus, 10 is a bindecimal number. The numbers 1010₁₀ = 1111110010₂ and 42₁₀ = 101010₁₀ 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):