단카 수
시간 제한8초메모리 제한512 MB
10진수 표기가 정확히 두 종류의 숫자로만 이루어진 양의 정수 중 N번째로 작은 수를 구한다. N은 10^18까지이며 데이터셋은 최대 100개다.
문제
願はくは 花の下にて 春死なむ そのきさらぎの 望月のころ
これは, 西行法師가 읊었다고 전해지는 유명한 단카 중 하나이다. 단카는 일본에서 오래전부터 사랑받아 온 와카의 한 종류로, 대부분 5·7·5·7·7의 다섯 구, 31음으로 이루어진다.
그런데 57577이라는 수는 5와 7, 두 종류의 숫자로만 이루어져 있다. 이처럼 십진 표기가 정확히 두 종류의 숫자로만 이루어진 양의 정수를 단카 수라고 부르기로 하자. 예를 들어 10, 12, 57577, 25252 등은 단카 수이지만, 5, 11, 123, 20180701 등은 단카 수가 아니다.
양의 정수 N이 주어진다. N번째로 작은 단카 수를 구하라.
입력
입력은 최대 100개의 데이터 세트로 이루어진다. 각 데이터 세트는 다음 형식으로 주어진다.
N
정수 N은 1 ≤ N ≤ 10^18을 만족한다.
입력의 끝은 0 하나로 이루어진 행으로 나타낸다.
출력
각 데이터 세트에 대해 N번째로 작은 단카 수를 한 줄에 출력하라.