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$$$).
3111007239
1 3 2 3 11 2 2 3 10 1 4 2 6 15 239
Here are the representations with the maximum number of zeros for the example test cases:
In the $$$239 = \mathtt{10E}_{15}$$$ representation, $$$\mathtt{E}$$$ stands for a digit with the value of $$$14$$$.
Name |
---|