1204. Idempotents

Time Limit: 1.0 second
Memory Limit: 16 MB
The number x is called an idempotent modulo n if
x*x = x (mod n)
Write the program to find all idempotents modulo n, where n is a product of two distinct primes p and q.

Input

First line contains the number K of test cases to consider (1 ≤ K ≤ 1000). Each of the following K lines contains one number n < 109.

Output

Write to the K-th line all idempotents of K-th test case in increasing order. Only nonnegative solutions bounded by n should be printed.

Sample

input output 
3
                        6
                        15
                        910186311
 
0 1 3 4
                        0 1 6 10
                        0 1 303395437 606790875
Problem Author: Pavel Atnashev
Problem Source: USU Internal Contest, March 2002

x^2=x(mod pq)
x(x-1)=0mod(pq)
有两个解0，1。
然后p|x且q|x-1或者p|x-1且q|x
设x=ap,x-1=bq或者x=aq,x-1=bp
解方程ap-bq=1
          或aq-bp=1
输出
URAL 1204