Zero or One

题目描述

给定一个不小于 $2$ 的整数 $N$，求不小于 $2$ 的整数 $b$ 的个数，使得：

当 $N$ 用以 $b$ 为底写出时，每一位数字都是 $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$ 个测试用例的答案。

3
12
2
36

4
1
5

提示

$1 \leq T \leq 1000$ $2 \leq N \leq 10^{18}$ 输入中的所有数值均为整数。对于第一个测试用例，有四个满足条件的 $b$：$b = 2, 3, 11, 12$。 确实，当 $N=12$ 用底 $2, 3, 11, 12$ 表示时，分别为 $1100, 110, 11$ 和 $10$。

标签: AtCoder|abc293F

来源

AtCoder|abc293F