Score : $500$ points

问题描述

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

• 当 $N$ 以 $b$ 进制表示时，每个数字均为 $0$ 或 $1$。

为 $T$ 个独立的测试用例求解答案。

可以证明，在本题约束条件下，满足条件的不小于 $2$ 的整数 $b$ 有有限个。

以上为通义千问 qwen-max 翻译，仅供参考。

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.

update @ 2024/3/10 12:12:53