Based Zeros
本题没有可用的提交语言。
Description
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.
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}$).
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$).
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$).
3
11
1007
239
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$.