"Brute Force isn't as inefficient as you may think", said the professor behind his mystical silhouette, as the final line before the end of the semester course.
The students chuckled amongst themselves, mistaking it for a joke. The gloomy Cryptography class had met its dead end, and the students submitted their final assignments: a digital lock fortified by a 512-bit variant of the SHA-2 encryption algorithm. As the students rose to leave, one of them, called Cal, stayed behind to notice something weird. He looked closely at the lock.
The lock had the 10(0-9) digits on its keypad, and it had a master key of N digits. The lock would break the moment someone entered the digits of the master key in succession. Cal remembered his own lock's master key: 1901. And he realized that the moment anyone entered those digits in succession, his lock would break. So as soon as someone entered a 1, followed immediately by a 9, followed immediately by a 0, and followed immediately by a 1... His lock would break. If someone entered a 1, and then entered something other than 9, then he had to start over. The digits before and after the required sequence would not really matter.
Cal's best friend interrupted his thoughts, "What are you thinking, dude?"
Cal turned back and replied, "See. We think our lock is entirely secure. Suppose we had a 2-digit code, you'd think that since there are a 100 2-digit numbers - consider 00-09 as two-digit numbers as well - you'd think you would require 200 digits to be assured that you tried all combinations. But it can be done in a much smaller sequence of digits."
"For instance, if I wanted to try all 2-digit combinations, I'd start with 0010203... And so on. This way, in 7 digits, I have covered 2-digit numbers like 00, 01, 02, 03, 10 and 20."
"And with sufficient foresight, I can calculate the shortest string that will cover all N-digit numbers, that is – if you tell me how long your master key is (let’s call that length N), I will give you the shortest string that is guaranteed to have all N-digit numbers as substrings. That will guarantee that your lock can be broken."(Caution: Numbers like 00000 or 00023 are 5-digit numbers in cryptographic contexts.)
Can you figure out what Cal was thinking?

Input
A number N which indicates how many digits are required to break upon the lock. You are supposed to process all these numbers until you read a 0 as input.
1 < N < 10
Output
The shortest string that has all possible N-digit strings as its substrings.
(Note: Outputs for the bigger numbers are huge.)

SAMPLE INPUT
1
2
0

SAMPLE OUTPUT
0123456789
0010203040..7787988990
(Case 2 is partially hidden. The first and last 10 digits of the smallest string are given.)

见题面

见题面