Description:


最近陶陶在研究数论,某天他偶然遇到一道题:对于给定的正整数 \(n\) ,求出下面这样一个式子的值:

\[ \sum_{i=1}^n \sum_{j=1}^n lcm(i, j)\]

其中 \(lcm(i, j)\) 表示正整数 \(i\)\(j\) 最小公倍数。
作为神犇的陶陶,当然轻松秒杀了这道题。不过他希望你写一个程序,用来检验他算的答案是否正确。

Input:


第一行包含一个正整数T,表示有T组测试数据。接下来 \(T\le 10^5\)
行,每行给出一个正整数 \(N,N\le 10^6\)

Output:


包含T行,依次给出对应的答案。

Sample Input:


Sample Output:


题解:


开始准备用 \(\mu\) 函数来做这道题结果发现会T。
然后去看题解才发现有这么巧妙的捉法。
一个性质:

\[ \sum_{i=1}^{n} [gcd(i, n) = 1] i = \frac {n\times phi(n)}{2}\]

然后就可以转化了:

整个式子都是很好筛出来的,然后每一次询问就 \(O(1)\) 了。
注意需要高精度,但是__int128就足够了。