Beibei aspires to be the strongest construction problem solver in FJ-ACM, so he practices construction problems diligently every day. To test the results of Beibei's training, Ningning proposed a problem that is extremely difficult to verify his learning progress:

Given a positive integer $n$, transform it into a perfect square within 100 operations. Each operation is defined as follows:

• Choose a divisor $x$ of the current number $n$, such that $n \pmod x = 0$.
• The chosen $x$ must be different from any $x$ chosen in previous operations.
• Then, update $n$ to $n + x$.

Throughout the process, $n$ is not allowed to exceed $10^{18}$.

This is too difficult for Beibei, so he found you, who are incredibly smart, to solve this problem.

Here, $n \pmod x$ denotes the remainder of $n$ divided by $x$.

Input

This problem contains multiple test cases.

The first line contains an integer $T$ ($1 \le T \le 10^3$), representing the number of test cases.

The following $T$ lines each contain a positive integer $n$ ($1 \le n \le 10^{12}$).

Output

For each test case:

The first line outputs an integer $m$ ($0 \le m \le 100$), representing the number of operations.

The second line contains $m$ distinct positive integers separated by spaces, representing the chosen numbers $x$ for each operation.

Throughout the process, you must ensure that $n$ does not exceed $10^{18}$.

Examples

Input 1

2
2025
182

Output 1

0
3
7 3 4

Note

The explanation for the first test case is as follows:

• Since $2025 = 45 \times 45$ is already a perfect square, no operations are needed.

The explanation for the second test case is as follows:

• First operation:
  • Choose $x = 7$, where $7$ is a divisor of $182$.
  • Let $n := 182 + 7 = 189$.
• Second operation:
  • Choose $x = 3$, where $3$ is a divisor of $189$ and $3$ is not in the set of previously chosen numbers $\{7\}$.
  • Let $n := 189 + 3 = 192$.
• Third operation:
  • Choose $x = 4$, where $4$ is a divisor of $192$ and $4$ is not in the set of previously chosen numbers $\{7, 3\}$.
  • Let $n := 192 + 4 = 196$.
  • $196 = 14 \times 14$ is a perfect square, finish.

Here, $:=$ denotes the assignment operator.