题目描述

给定一个不小于 $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$。