Leonhard Euler (1707-1783) was a great mathematician. In this problem, we will consider one of the functions named in his honor, namely Euler's totient function $\varphi$.

The value of the function $\varphi$ for a natural number $n$ is the number of integers $k$ ($1 \le k \le n$) that are coprime to $n$. Two numbers are coprime if they have no common divisor greater than 1. For example, $\varphi(6) = 2$, because the numbers 1 and 5 are coprime to 6, while the numbers 2, 3, 4, and 6 are not.

A problem that Euler might have asked if he were still alive could be the following: for a given natural number $n$, find all natural numbers $x$ that satisfy the equation $\varphi(x) = n$.

Input

The first line of input contains a single natural number $t$ ($1 \le t \le 5$) specifying the number of test cases. The following $t$ lines contain descriptions of the test cases. Each description contains a single natural number $n$ ($1 \le n \le 10^{10}$).

Output

Your program should output the answers for each test case in the order they appear in the input. The answer for each test case consists of two lines. The first line should contain the number of solutions. The second line should contain all solutions to the equation in increasing order. If the equation has no solutions, the second line of the answer for the test case should be left empty.

Examples

Input 1

4
8
10
13
6

Output 1

5
15 16 20 24 30
2
11 22
0

4
7 9 14 18