AT_jsc2023_final_c Power Convergence

给定一个整数 $N$。 对于正整数 $x$，定义 $f(x)$ 如下： - 考虑满足 $x^k \equiv x^{k+1} \bmod N$ 的非负整数 $k$。如果存在这样的 $k$，则 $f(x)$ 为满足条件的最小 $k$；若不存在，则 $f(x)=0$。 请计算 $\sum_{1 \leq x \leq N} f(x)$ 的值。 对于一个输入文件中的所有 $T$ 个测试用例，请分别作答。

输入由标准输入以以下格式给出。 > $T\ case_1\ case_2\ \cdots\ case_T$ 每个测试用例 $case_i$ 的格式如下： > $N$

输出 $T$ 行，第 $i$ 行输出对应 $case_i$ 的答案。

### 样例解释 1 例如 $N=4$ 时，$f(x)$ 的值如下所示： - $f(1)=0\ \ \ \ $（$1^0 \equiv 1^1 \bmod 4$） - $f(2)=2\ \ \ \ $（$2^2 \equiv 2^3 \bmod 4$） - $f(3)=0\ \ \ \ $（不存在满足 $3^k \equiv 3^{k+1} \bmod 4$ 的 $k$） - $f(4)=1\ \ \ \ $（$4^1 \equiv 4^2 \bmod 4$） 所以答案为 $0+2+0+1=3$。 ### 数据范围 - $1 \leq T \leq 10$ - $2 \leq N \leq 10^9$ - 输入的值均为整数。 由 ChatGPT 5 翻译