시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 17 12 3 42.857%

문제

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.

예제 입력

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

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