Problem 1óDouble Trouble


The secret service of Hudonia has always had a strong appetite for strange numbers. This appetite seemed strongest when Hudonia was in trouble. The numbers they were looking for had the following property. Whenever you would right-rotate the number (that is, take away the last digit and put it in front of the number), you would end up with double the original number. Numbers possessing this property were called double-trouble numbers. For example, X = 421052631578947368 is a double-trouble number, since 2X = 842105263157894736 which is a right rotation of X.

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.


INPUT SPECIFICATION.The input file will contain a series of integers inclusively between 2 and 200 corresponding to the base for which you are to compute the smallest double-trouble number.The last number in the file will be 0, signifying the end of input.Each number will be followed by <EOLN>.There will be no additional spaces or <EOLN>'s in the file.


OUTPUT SPECIFICATION.The output cases should be processed in the order in which they appear in the input file.For each input case, print out the smallest double-trouble number for that base using the exact format demonstrated below.Notice that since it is difficult to express digits for bases greater than 10, we instead use for each digit the decimal number corresponding to that digit followed by a space.Make sure that the introductory line to each answer is exactly as demonstrated.Each output case should be followed by an extra <EOLN> character.