이진법과 십진법

양의 정수의 십진법 표기가 그 수의 이진법 표기의 접미사와 같으면, 그 수를 이진십진수라고 한다. 십진법 표기와 이진법 표기 모두 앞자리 0은 붙이지 않는다.

예를 들어 $10_{10} = 1010_2$ 이고 십진법 표기 10은 이진법 표기 1010의 마지막 두 자리와 같으므로, 10은 이진십진수다. 반면 $1010_{10} = 1111110010_2$ 이고 1010은 1111110010의 접미사가 아니므로 1010은 이진십진수가 아니다. $42_{10} = 101010_2$ 도 42가 101010의 접미사가 아니므로 이진십진수가 아니다.

$n$번째로 작은 이진십진수를 구하라.

첫째 줄에 정수 $n$이 주어진다. ($1 \le n \le 10000$)

$n$번째로 작은 이진십진수를 십진법으로 출력한다.

이진법 표기에는 0과 1만 나오므로, 이진십진수의 십진법 표기에도 0과 1만 나온다. 십진법 표기가 0과 1로만 이루어진 수를 작은 것부터 나열하면 다음과 같다.