In this problem we recall the great mathematician Leonhard Euler (1707 - 1783) and investigate his well-known totient function fi(n).

The value of fi(n) for positive integer n is the number of integers k (1 ≤ k ≤ n) that are coprime with n. Two integers are called coprime if their only common positive divisor is 1. For example, we have fi(6) = 2, since 1 and 5 are coprime with 6, whereas 2, 3, 4 and 6 are not.

A problem that could have been stated by Euler is as follows: given a positive integer n, find all positive integers x that satisfy the equation: fi(x) = n.

Input

The first line contains one integer t (1 ≤ t ≤ 5) that denotes the number of test cases. t lines follow with descriptions of respective test cases. Each such description consists of a single integer n (1 ≤ n ≤ 1010).

Output

Your program should output the answers to the respective test cases. For each test case it should write two lines. The first line should contain the number of solutions of the equation. The second line should contain all solutions listed in increasing order. If the equation does not have any solution, for the corresponding test case your program should write an empty second line.