C. Continued Fractions
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Continued fractions are a powerful mathematical tool. They are however, too complicated, so we have created our own definition.

Let $$$(a, b)$$$ be a pair of positive integers. We call the sequence $$$\left \{\frac{a+n}{b+n} \right\}_{n=0}^{\infty}$$$ the continued fractions of the pair $$$(a, b)$$$. For example, if $$$a = 14$$$ and $$$b = 2$$$, the sequence of continued fractions begins with $$$\frac{14}{2}$$$, $$$\frac{15}{3}$$$, $$$\frac{16}{4}$$$, $$$\frac{17}{5}$$$, $$$\frac{18}{6}$$$, $$$\frac{19}{7}$$$.

Note that if $$$a \neq b$$$ the sequence of continued fractions contains only a finite number of integers. In the above example, the elements that are integers are those with indices $$$n = 0, 1, 2, 4, 10$$$.

We define the integrity of a pair of integers $$$(a, b)$$$ to be the length of the longest prefix of the sequence of continued fractions that contains only integers. For example $$$\textrm{integrity}(14, 2) = 3$$$.

You are given a positive integer $$$p$$$. Your task is to find and report all pairs of integers $$$(a, b)$$$ that satisfy the following two conditions:

  • $$$\frac{a}{b} = p$$$
  • $$$\textrm{integrity}(a, b) \geq 3$$$
Input

The first line of input contains a single integer $$$t$$$ ($$$1 \leq t \leq 20$$$) — the number of test cases.

$$$t$$$ lines follow (one for each test case), the $$$i$$$-th of which ($$$1 \leq i \leq t$$$) is containing a single integer $$$p_i$$$ ($$$2 \leq p_i \leq 10^{18}$$$) — corresponding to the $$$p$$$ from the description above.

Output

For each test case, first output one line containing a single integer $$$k$$$  – the number of pairs $$$(a, b)$$$ satisfying the two conditions from the problem statement. Then output $$$k$$$ integers $$$b_1, b_2, \dots, b_k$$$ — the values of $$$b$$$ sorted in ascending order.

Note that under the constraints of the problem it can be shown that the sum of all $$$k$$$ is at most $$$100\,000$$$.

Example
Input
1
7
Output
2
1 2