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

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

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

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

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

有限次调用 Sp 函数之后，可以得到一组 Sp 函数调用的解，定义 Sum 函数 = 函数值的和，即 Sum = Sp(a_1,b_1)+Sp(a_2,b_2)+...+Sp(a_m,b_m)。

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

简单地说：机器需要对给定的数堆有限次调用 Sp 函数使数堆变成只有一个 1，然后尽可能地使结果 Sum 最大。

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

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

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