DOUBLE - Doubled Numbers

Some numbers have a curious property: when rotating the number to the right, the new number is the double of the original. Rotating the number to the right means choosing the last digit and moving it to the beginning of the number, as the leftmost digit. For example, the number 421052631578947368 when rotated to the right gives 842105263157894736, which is the double of the original. These numbers are expressed in the decimal system. In any numeral system such numbers exist, for example, in the binary (base 2) numeral system, numbers 01 and 0101 have this property. Note that leading zeros are required in this case.

Write a program that, for any given base B (2 <= B <= 250), finds the smallest number in that numeral system which has this property. Try not to precompute the numbers, the solution is very easy and pretty.

Input

The input consists of several test cases. The first line contains an integer T (T <= 20), the number of test cases. The following T lines contain one number B, each.

Output

For each number B, output one or more numbers separated by a blank space that represent the digits in base B (written as decimal numbers) of the smallest number which has this property.

Example

Input:
3
2
10
35

Output:
0 1
0 5 2 6 3 1 5 7 8 9 4 7 3 6 8 4 2 1
11 23

Output explanation

In example #1:

The initial number (when converted to decimal system): 0 * 2^1 + 1 * 2^0 = 1

After applying the rotation: 1 * 2^1 + 0 * 2^0 = 2.

In example #3:

The initial number (when converted to decimal system): 11 * 35^1 + 23 * 35^0 = 408

After applying the rotation: 23 * 35^1 + 11 * 35^0 = 816.


Added by:Reinier César Mujica Hdez
Date:2008-11-10
Time limit:1s
Source limit:3072B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:OCI Olimpiads Cuban in Informatics 2008 day 1

hide comments
2012-06-12 21:33:30 akb
Nice Question,Good for Learning...
2011-01-29 16:59:37 J
How to find the unit's digit of the solution number?. If this is done, then the problem can be solved easily.
2011-01-16 15:18:57 The Bartender
Nice problem!
(gracias por compartir!)

Last edit: 2011-01-16 15:26:45
2009-03-02 08:44:29 Paul Draper
0 works. (or 00)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.