AT_abc293_f [ABC293F] Zero or One

题目描述

给定一个不小于 $2$ 的整数 $N$。请输出满足下述条件的 $2$ 以上的整数 $b$ 的个数：

• 当用 $b$ 进制表示 $N$ 时，所有的数位都为 $0$ 或 $1$。

对于 $T$ 个独立的测试用例，请分别给出答案。

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

输入格式

输入以如下格式从标准输入给出。这里，$\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

输入 #1

3
12
2
36

输出 #1

4
1
5

说明/提示

约束

• $1 \leq T \leq 1000$
• $2 \leq N \leq 10^{18}$
• 所有输入均为整数

样例解释 1

对于第 $1$ 个测试用例，满足题目条件的 $b$ 有 $b=2,3,11,12$ 共 $4$ 个。实际上，$N=12$ 用 $2,3,11,12$ 进制分别表示为 $1100,110,11,10$。

由 ChatGPT 4.1 翻译