The number X is a double-trouble number in the number system with base 10. Any number system with base p >= 2, however, has many such double-trouble numbers. In the binary number system (base p = 2), for example, we have the double-trouble numbers 01 and 0101. Notice that the leading zeros are necessary here in order to obtain the proper number after right rotation.

The secret service seemed to like the smallest double-trouble numbers in a number system most. For example, in the binary number system the smallest double-trouble number is 01. In the decimal (p = 10) number system, the smallest double-trouble number is 052631578947368421. Being a patriotic Hudonian, you are asked to write a program that computes for a given base p of a number system the smallest double-trouble number in that system.

The input file consist of a sequence of numbers, one per line, ended by end-of-file. Each number is less than 200. The output file consists of, for each number p in the input file, the smallest double-trouble number (including any necessary leading zeros) in the number system with base p. The double-trouble numbers are given in the format analogous to the example below and in the same order as in the input file. No blank line should appear at the end of the output. Digits in a base-p number system are given in decimal representation, and each digit (including the last one) is followed by a single space.

Sample Input

2 10 35

Sample Output

For base 2 the double-trouble number is
0 1
For base 10 the double-trouble number is
0 5 2 6 3 1 5 7 8 9 4 7 3 6 8 4 2 1
For base 35 the double-trouble number is
11 23