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.

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⁹.

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.