/ 
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
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
1 番目のテストケースについて、問題文中の条件を満たす b は、b = 2, 3, 11, 12 の 4 つです。 実際、N = 12 を 2, 3, 11, 12 進法で表すと、それぞれ 1100, 110, 11, 10 となります。
Score : 500 points
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.