B. Based Zeros
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Barbara has always known how to represent integers in the decimal numeral system (base ten), using digits $$$0, 1, 2, \ldots, 9$$$. Recently she has learned that for any integer base $$$b \ge 2$$$, she can also represent integers in base $$$b$$$, using symbols with values from $$$0$$$ to $$$b-1$$$, inclusive, as digits.

Barbara's favorite digit is $$$0$$$. Luckily, it looks the same in all bases.

Today Barbara is playing with a positive integer $$$n$$$. Now she wonders: in what bases does the representation of $$$n$$$ contain the biggest number of zeros? Help her to find all such bases.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 1000$$$). The description of the test cases follows.

The only line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 10^{18}$$$).

Output

For each test case, in the first line, print two integers $$$k$$$ and $$$m$$$, denoting the maximum number of zeros the representation of $$$n$$$ can have in any integer base, and the number of such bases, respectively.

In the second line, print $$$m$$$ integers $$$b_1, b_2, \ldots, b_m$$$, denoting all such bases in increasing order ($$$2 \le b_1 < b_2 < \cdots < b_m \le n$$$).

Example
Input
3
11
1007
239
Output
1 3
2 3 11
2 2
3 10
1 4
2 6 15 239
Note

Here are the representations with the maximum number of zeros for the example test cases:

  • $$$11 = \mathtt{1011}_2 = \mathtt{102}_3 = \mathtt{10}_{11}$$$ (one zero);
  • $$$1007 = \mathtt{1101022}_3 = \mathtt{1007}_{10}$$$ (two zeros);
  • $$$239 = \mathtt{11101111}_2 = \mathtt{1035}_6 = \mathtt{10E}_{15} = \mathtt{10}_{239}$$$ (one zero).

In the $$$239 = \mathtt{10E}_{15}$$$ representation, $$$\mathtt{E}$$$ stands for a digit with the value of $$$14$$$.