안전 금고의 잠금 해제 코드

보안 하드웨어 분야를 선도하는 KEY 사(社)가 새로운 금고를 개발했다. 이 금고는 열쇠가 아니라 키패드에 올바른 $n$자리 코드를 입력해야 열린다. 어린이용 장난감 금고(2자리 코드)부터 군용 모델(6자리 코드)까지 여러 종류가 있다.

올바른 코드의 마지막 자리를 누르는 순간 금고가 열린다. 별도의 "입력(Enter)" 키는 없다. $n$자리보다 많이 누르면 마지막 $n$자리만 의미가 있다. 예를 들어 4자리 버전에서 올바른 코드가 4567이고 1234567890을 차례로 누른다면, 7을 누르는 순간 문이 열린다.

내부적으로 금고는 항상 $10^{n-1}$개의 상태 중 하나에 있으며, 현재 상태는 가장 최근에 입력한 $n-1$자리를 뜻한다. 이 상태들 중 하나(예시에서는 456)가 열림 상태로 지정되어 있다. 금고가 열림 상태일 때 올바른 키(예시에서는 7)를 누르면 문이 열리고, 그렇지 않으면 새로운 상태로 이동한다. 예를 들어 상태 456에서 8을 누르면 상태 568로 바뀐다.

금고를 여는 단순한 방법은 가능한 모든 코드를 하나씩 입력하는 것인데, 최악의 경우 $n \cdot 10^n$번의 타건이 필요하다. 하지만 숫자열을 잘 고르면 최대 $10^n + n - 1$번의 타건만으로 반드시 금고를 열 수 있다. 필요한 것은 모든 $n$자리 수열을 정확히 한 번씩 포함하는 숫자열을 찾는 것뿐이다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 정수 $n$ 하나로 주어지며 $1 \le n \le 6$이다. 마지막 테스트 케이스 다음 줄에는 0이 주어지며, 이 값은 처리하지 않는다.

각 테스트 케이스 $n$에 대해 한 줄을 출력한다: 모든 $n$자리 수열이 연속된 부분 문자열로 정확히 한 번씩 나타나는, 길이 $10^n + n - 1$인 숫자(0–9) 수열 중 사전순으로 가장 작은 것.