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* < 10^{9}.

### 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