循环的映射

时间限制：$5s$

空间限制：$256MB$

题目背景

首先，让我们定义两个集合。$Z_n =\{0,1,2,...,n-1\}, F=\{f|y=f(x), x∈Z_n,y∈Z_n\}$是从$Z_n$到$Z_n$的一一对映。不难得出 F 中有$n!$ 个元素，元素 f 也可以理解成 0 到 n - 1 这 n 个数字所有的排列方案。

现在，我们在定义两个集合中元素的运算。定义 $a + b(a,b ∈Z_n)$是模 n 意义下的加法，$f_a+f_b= f_a ( f_b (x))\quad (f_a, f_b∈F)$也就是两个函数的复合。对于 n 个相同的f相加，我们可以写成$f^{(n)}=f+f+f+…+f$。

可以发现，大部分的f是很没有意思的，相当于把n个数字随机打乱，因此我们现在要重点研究一种 f。定义$F^*=\{f|f(a)+f(b)=f(a+b)\quad(a,b ∈Z_n)\}$，也就是说这种经过这种f可以使得$Z_n$中的元素运算规律保持不变。例如f(x)=x也就是保持不变就是一种符合条件的函数。

另外一方面，从函数嵌套的角度。$A=\{x|x= f^{(n)}\quad (n \in N)\}$，这样可以生成一个有限集合，不妨记作$A(f)$。或者 A 和 B 都是元素为 f 的集合，那么可以有定义 $C=A*B=\{f|f= f_a+f_b(f_a∈A,f_b∈B)\}$。这些集合都是F的子集。

对于F，你既可以当成$Z_n$的自我映射，也可以当成是对一些元素的排序，不难发现这很有研究价值。

题目描述

小陆最近对这样的集合与运算很感兴趣，他希望你帮忙研究一个问题。已知n，对于一个由$Z_n$产生出的$F^*$，对于每一个$f∈F^*$，都可以找到一个B ⊆F，使得$F^*⊆ B*A(f)$。现在，小陆需要你考虑当B的元素个数最小时，对于所有的$f∈F^*$，B的元素个数的总和。

(省流版：$F^*=Aut\quad Z_n, f∈F^*, A=\{x|x=f^{(n)}\}$，求所有 $f$ 的$| F^*/A|$之和)

输入格式

第一行一个正整数 T，表示测试样例数。

第二行 T 个正整数，每个数就是对应的 $n$。

输出格式

T 个正整数，就是所求的答案。

样例

输入:

3
1 3 114

输出：

1 3 210

样例解释

对于第一个样例，$F^*$里只有$x=f(x)$，$A(f)$也为$\{x=f(x)\}$，那么可以找到B也为 $\{x=f(x)\}$，$A*B={x=f(x)}= F^*$。

对于第二个样例，$F^*=\{f_1,f_2\}$，其中$f_1$为$(0\rightarrow 0, 1 \rightarrow 1, 2 \rightarrow 2)$, $f_2$为$(0\rightarrow0, 1\rightarrow2,2\rightarrow1)$。$A(f_1)=\{f_1\}, A(f_2)=\{f_1, f_2\}$。可以找到 B 分别为$\{f_1, f_2\}$和${f_1}, \{f_1, f_2\}*\{ f_1\}=\{f_1, f_2\}= F^*$，因此答案为 $1+2=3$。

数据范围与约定

对于$20\%$的数据, $T=1，n\le10$

对于$40\%$的数据, $T=10，n\le100$

对于$60\%$的数据, $T=100，n\le10000$

对于$100\%$的数据, $T=1000，n\le30000$