The number x is called an idempotent modulo n if
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 on the i-th line all idempotents of i-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