配点 : 700 点
問題文
整数 N 。 对于
正整数 x , 定义f(x) 如下。
- 非負整数 k 和 考虑一下x^k \equiv x^{k+1} \mod N 的情况。 像这样 如果 k 存在,则其最小值为 f(x) 。 如果它不存在 查找 f(x)=0 。
\sum_{1 \leq x \leq N} f(x) 。
1 对于一个输入文件, 请回答T 测试用例。
制約
- 1 \leq T \leq 10
- 2 \leq N \leq 10^9
- 所有输入值都是整数。
入力
输入将以以下格式从标准输入给出。
T case_1 case_2 \vdots case_T
每个测试用例 case_i 具有以下格式。 输出
N
出力
T 行。 打印 i 在线 case_i 的答案。 当
入力例 1
10 2 3 4 5 6 7 8 9 10 11
出力例 1
1 1 3 1 3 1 9 5 3 1
例如 N=4 什么时候 f(x) 的值如下。 满足
- f(1)=0\ \ \ \ (1^0 \equiv 1^1 \mod 4)
- f(2)=2\ \ \ \ (2^2 \equiv 2^3 \mod 4)
- f(3)=0\ \ \ \ (3^k \equiv 3^{k+1} \mod 4 满足 k 不存在)
- f(4)=1\ \ \ \ (4^1 \equiv 4^2 \mod 4)
因此,答案是 0+2+0+1=3 。
入力例 2
10 91 92 93 94 95 96 97 98 99 100
出力例 2
3 7 3 3 3 119 1 27 11 31