9251: ABC293 —— F - Zero or One
[Creator : ]
Description
### Problem Statement
Given an integer $N$ not less than $2$, find the number of integers $b$ not less than $2$ such that:
- when $N$ is written in base $b$, every digit is $0$ or $1$.
Find the answer for $T$ independent test cases.
It can be proved that there is a finite number of desired integers $b$ not less than $2$ under the constraints of this problem.
Given an integer $N$ not less than $2$, find the number of integers $b$ not less than $2$ such that:
- when $N$ is written in base $b$, every digit is $0$ or $1$.
Find the answer for $T$ independent test cases.
It can be proved that there is a finite number of desired integers $b$ not less than $2$ under the constraints of this problem.
Input
### Input
The input is given from Standard Input in the following format, where $\mathrm{test}_i$ denotes the $i$-th test case:
```
$T$
$\mathrm{test}_1$
$\mathrm{test}_2$
$\vdots$
$\mathrm{test}_T$
```
Each test case is given in the following format:
```
$N$
```
The input is given from Standard Input in the following format, where $\mathrm{test}_i$ denotes the $i$-th test case:
```
$T$
$\mathrm{test}_1$
$\mathrm{test}_2$
$\vdots$
$\mathrm{test}_T$
```
Each test case is given in the following format:
```
$N$
```
Output
### Output
Print $T$ lines. For $i = 1, 2, \ldots, T$, the $i$-th line should contain the answer to the $i$-th test case.
Print $T$ lines. For $i = 1, 2, \ldots, T$, the $i$-th line should contain the answer to the $i$-th test case.
Constraints
### Constraints
- $1 \leq T \leq 1000$
- $2 \leq N \leq 10^{18}$
- All values in the input are integers.
- $1 \leq T \leq 1000$
- $2 \leq N \leq 10^{18}$
- All values in the input are integers.
Sample 1 Input
3
12
2
36
Sample 1 Output
4
1
5
For the first test case, four $b$'s satisfy the condition in the problem statement: b=2,3,11,12. Indeed, when N=12 is written in base 2,3,11 and 12, it becomes 1100,110,11 and 10, respectively.