零或一

题目描述

给定一个不小于 $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$ 行（$i = 1, 2, \ldots, T$）输出第 $i$ 个测试用例的答案。

样例

3
12
2
36

4
1
5

对于第一个测试用例，满足条件的 $b$ 有四个：$b = 2, 3, 11, 12$。 确实，$N = 12$ 写成 $2, 3, 11$ 和 $12$ 进制时，分别为 $1100, 110, 11$ 和 $10$。

数据范围

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