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.</p>

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.

예제 입력 1

1

예제 출력 1

1

예제 입력 2

2

예제 출력 2

10

예제 입력 3

10

예제 출력 3

1100

힌트

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):