102935: [Atcoder]ABC293 F - Zero or One

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.

Constraints

• $1 \leq T \leq 1000$
• $2 \leq N \leq 10^{18}$
• All values in the input are integers.

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$

Output

Print $T$ lines. For $i = 1, 2, \ldots, T$, the $i$-th line should contain the answer to the $i$-th test case.

Sample Input 1

3
12
2
36

Sample Output 1

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.

问题描述

给定一个不小于2的整数$N$，找出所有不小于2的整数$b$，满足以下条件：

• 当$N$用基数$b$表示时，每个数字都是0或1。

为T个独立的测试用例找到答案。

可以证明，在此问题的约束下，所求的不小于2的整数$b$的数量是有限的。

约束

• $1 \leq T \leq 1000$
• $2 \leq N \leq 10^{18}$
• 输入中的所有值都是整数。

输入

输入从标准输入按以下格式给出，其中$\mathrm{test}_i$表示第i个测试用例：

$T$
$\mathrm{test}_1$
$\mathrm{test}_2$
$\vdots$
$\mathrm{test}_T$

每个测试用例按以下格式给出：

$N$

输出

打印T行。 对于$i = 1, 2, \ldots, T$，第i行应包含第i个测试用例的答案。

样例输入1

3
12
2
36

样例输出1

4
1
5

对于第一个测试用例，有四个$b$满足问题描述中的条件：$b = 2, 3, 11, 12$。 事实上，当$N=12$用基数$2, 3, 11$和$12$表示时，分别变为$1100, 110, 11$和$10$。