← 返回题目列表

AtCoder · jsc2023_final_c

C. 力量汇聚

中文机器翻译题面 查看原题

配点 : 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