L. Equation
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Given an integer $$$M$$$, find all integer values of $$$x$$$ that satisfy the following conditions:

$$$$$$ \left\{ \begin{aligned} & x^2 \equiv x \pmod{M} \\ & 0 \leq x \lt M \end{aligned} \right. $$$$$$

where $$$A \equiv B \pmod{M}$$$ denotes that expression $$$A$$$ is congruent to expression $$$B$$$ modulo $$$M$$$, meaning that the remainders of both sides when divided by $$$M$$$ are equal.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$T$$$ ($$$1 \leq T \leq 1000$$$). For each test case:

The only line contains only one integer $$$M$$$ ($$$1 \le M \le 10^9$$$) .

Output

For each test case, output two lines:

The first line outputs an integer $$$n$$$, representing the number of solutions to the equation.

The second line outputs $$$n$$$ integers, listing the solutions in ascending order separated by spaces.

Example
Input
4
6
114514
20231126
1
Output
4
0 1 3 4
8
0 1 22165 35093 57257 57258 79422 92350
4
0 1 10115563 10115564
1
0
Note

In the first test case of example:

$$$0^2=0+0 \times 6$$$,

$$$1^2=1+0 \times 6$$$,

$$$2^2=4+0 \times 6$$$,

$$$3^2=3+1 \times 6$$$,

$$$4^2=4+2 \times 6$$$,

$$$5^2=1+4 \times 6$$$,

So, there are four solutions in total, which are $$$0,1,3$$$ and $$$4$$$.