CODE - Code

## 题面 KEY 公司开发出一种新的保险箱。要打开保险箱，不需要钥匙，但需要输入一个正确的、由 n 位数字组成的编码。这种保险箱有几种类型，从给小孩子玩的玩具（2 位数字编码）到军用型的 保险箱（6 位数字编码）。 当正确地输入最后一位编码后，保险箱就立刻打开了。保险箱上没有“确定”键。当你输入 超过 n 位数字，则只有最后 n 位数字有效。例如，对一种 4 位数字编码的型号，如果正确的编码 为 4567，你想输入的编码为 1234567890，则保险箱的门会在你输入数字 7 后马上就打开了。 为了达到这种效果所需要设计的软件其实很简单。对 n 位数字编码的型号，保险箱始终处于 10^(n-1)种内部状态之一。保险箱的当前状态只需用最后输入的 n-1 位数字表示，其中有一种状态（例 如，对前面的例子，就是 456）被记为“开锁状态”。如果保险箱处于“开锁状态”，且输入最后 一位正确的数字（例如，在上面的例子中就是 7），保险箱的门就打开了；否则保险箱切换到对应 的新状态。例如，如果保险箱的当前状态为 456，接着输入 8，则保险箱的状态切换到 568。 为了开保险箱，一个繁琐的策略是一位接一位地输入所有可能的编码。然而，在最坏情况下， 这需要按键 n×10^n次（有 10n组可能的编码，每个编码有 n 位）。而选择一个好的数字序列，最 多只需要按键 10^n+ n - 1 次就可以打开保险箱了：你需要做的就是找到一个数字序列包含所有的 n 位数一次且仅一次。KEY 公司宣称，对军用型号（n = 6），当今最快的计算机也需要数十亿年 的时间才能找到这样的数字序列，但是很显然他们不知道有些程序员能在几分钟就能找到这样的 数字序列。 ## 输入描述： 输入文件中包含多个测试数据。每个测试数据为一个整数 n，1≤n≤6。输入文件最后一行为 0，表示输入结束。 ## 输出描述： 对输入文件中的每个测试数据，输出一行包含 10^n + n - 1 位的数字序列，使得每个 n 位数出 现一次且仅一次。

KEY Inc., the leading company in security hardware, has developed a new kind of safe. To unlock it, you don't need a key but you are required to enter the correct `n`-digit code on a keypad (as if this were something new!). There are several models available, from toy safes for children (with a 2-digit code) to the military version (with a 6-digit code). The safe will open as soon as the last digit of the correct code is entered. There is no "enter" key. When you enter more than `n` digits, only the last `n` digits are significant. For example (in the 4-digit version), if the correct code is 4567, and you plan to enter the digit sequence 1234567890, the door will open as soon as you press the 7 key. The software to create this effect is rather simple. In the `n`-digit version the safe is always in one of `10 $ ^{n-1} $ ` internal states. The current state of the safe simply represents the last `n-1` digits that have been entered. One of these states (in the example above, state 456) is marked as the `unlocked` state. If the safe is in the unlocked state and then the right key (in the example above, 7) is pressed, the door opens. Otherwise the safe shifts to the corresponding new state. For example, if the safe is in state 456 and then you press 8, the safe goes into state 568. A trivial strategy to open the safe is to enter all possible codes one after the other. In the worst case, however, this will require `n * 10 $ ^{n} $ ` keystrokes. By choosing a good digit sequence it is possible to open the safe in at most `10 $ ^{n} $ + n - 1` keystrokes. All you have to do is to find a digit sequence that contains all `n`-digit sequences exactly once. KEY Inc. claims that for the military version (n=6) the fastest computers available today would need billions of years to find such a sequence - but apparently they don't know what some programmers are capable of...