1080. 超消函数

生活于红色沼泽中心的数学家发现了一个不得了的函数。

定义超消函数的函数值 Sp(a,b)=gcd(a,b)Sp(a,b) =gcd(a,b)

gcd(x,y)gcd(x,y)x,yx,y 的最大公因数。

定义原始数堆为 nn 个范围在 [1,n][1,n] 并且两两不相同的数,即长度为 nn 的置换数列。

红沼区的数学家发现,对原始数堆进行一次超消函数竟然能把两个参数去除掉,并且把两个参数 aabbgcd(a,b)gcd(a,b) 加入新数列中,比如 Sp(4,6)=2Sp(4,6) = 2,数堆中的 4466 都消失了,并且多了一个 22

有限次调用 SpSp 函数之后,可以得到一组 SpSp 函数调用的解,定义 SumSum 函数 == 函数值的和,即 Sum=Sp(a1,b1)+Sp(a2,b2)+...+Sp(am,bm)Sum = Sp(a_1,b_1)+Sp(a_2,b_2)+...+Sp(a_m,b_m)

他非常兴奋自己竟然发现了这样神奇的函数。他制造了一个机器,机器能够得到数堆的最大的 SumSum 函数。

简单地说:机器需要对给定的数堆有限次调用 SpSp 函数使数堆变成只有一个 11,然后尽可能地使结果 SumSum 最大。

输入

第一行输入一个 T (1T20)T \ (1 \leq T \leq 20),表示有 TT 组数据。

接下来的 TT 行,每行输入一个 n (1n10000)n \ (1 \leq n \leq 10000),表示数堆大小。

输出

每组数据单独输出一行结果,表示该组数组能得到的最大的 SumSum

样例

标准输入 复制文本
2
2
4
标准输出 复制文本
1
4

来源

广东工业大学 2020 年 ACM 第一次月赛

登录以提交代码。
单点时限 1 秒
内存限制 128 MB
提交 319
通过 174