Safe Unlock Code

KEY Inc., a leading maker of security hardware, has built a new kind of safe. To open it you do not use a key; instead you must type the correct $n$-digit code on a keypad. Models range from toy safes for children (a 2-digit code) up to the military version (a 6-digit code).

The safe opens the instant the last digit of the correct code is entered — there is no "Enter" key. If you type more than $n$ digits, only the last $n$ digits matter. For example, in the 4-digit version, if the correct code is 4567 and you type the sequence 1234567890, the door opens the moment you press 7.

Internally the safe is always in one of $10^{n-1}$ states, where the current state is simply the last $n-1$ digits entered. One of these states (456 in the example) is marked as the unlocked state. If the safe is in the unlocked state and the correct next key (7 in the example) is pressed, the door opens; otherwise the safe moves to a new state. For example, from state 456, pressing 8 moves the safe to state 568.

A naive way to open the safe is to try every code in turn, which in the worst case needs $n \cdot 10^n$ keystrokes. With a well-chosen digit sequence, however, you can guarantee the safe opens after at most $10^n + n - 1$ keystrokes: all you need is a digit sequence that contains every $n$-digit sequence exactly once.

The input contains several test cases. Each test case is a single integer $n$ with $1 \le n \le 6$. The last test case is followed by a line containing 0, which must not be processed.

For each test case $n$, print a single line: the lexicographically smallest sequence of $10^n + n - 1$ digits (each digit 0–9) in which every $n$-digit sequence occurs exactly once as a contiguous substring.