首先把 $\operatorname{lcm}$ 转化成 $\gcd$，即 $n\sum\limits_{i=1}^n\dfrac i{\gcd(i,n)}$。

将上式翻转相加，可得

$$\begin{aligned} & \dfrac n2\left[\sum\limits_{i=1}^{n-1}\dfrac i{\gcd(i,n)}+\sum\limits_{i=1}^{n-1}\dfrac{n-1}{\gcd(n-i,n)}\right]+n \\ = & \dfrac n2\left[\sum\limits_{i=1}^{n-1}\dfrac i{\gcd(i,n)}+\sum\limits_{i=1}^{n-1}\dfrac{n-1}{\gcd(n-i,n)}\right]+n \\ = & \dfrac n2\left[\sum\limits_{i=1}^n\dfrac n{\gcd(i,n)}\right]+\dfrac n2. \\ \end{aligned} $$

考虑枚举 $d=\gcd(i,n)$ 的值，则上式中的 $\sum$ 部分即为 $\sum\limits_{d|n}\dfrac nd\cdot\varphi\left(\dfrac nd\right)=\sum\limits_{d|n}d\cdot\varphi(d)$。

显然 $f(n)=\sum\limits_{d|n}d\cdot\varphi(d)$ 是一个积性函数，考虑使用线性筛预处理出 $f(n)$。

对于素数 $p$ 和正整数 $k$，有 $f\left(p^{k+1}\right)=f\left(p^k\right)+p^{k+1}\cdot\varphi\left(p^{k+1}\right)=f\left(p^k\right)+p^{2k+1}(p-1)$。

为了使用线性筛，要将一个数乘上一个它没有的素因子是容易实现的，所以下面考虑给它乘上一个它已经有的素因子。

设 $x=a\cdot p^{k+1}$，其中 $p\nmid a$，则 $f\left(ap^{k+1}\right)=f(a)f\left(p^{k+1}\right)$，$f\left(ap^k\right)=f(a)f\left(p^k\right)$，可得 $f\left(ap^{k+1}\right)-f\left(ap^k\right)=f(a)\left[f\left(p^{k+1}\right)-f\left(p^k\right)\right]=f(a)\cdot p^{2k+1}(p-1)$。

同理可得 $f\left(ap^k\right)-f\left(ap^{k-1}\right)=f(a)\cdot p^{2k-1}(p-1)$，所以 $f\left(ap^{k+1}\right)-f\left(ap^k\right)=p^2\left[f\left(ap^k\right)-f\left(ap^{k-1}\right)\right]$。

此时，我们已经可以用线性筛预处理出 $f(n)$ 的值了。

时间复杂度 $\Theta(T+\max n)$。

/* 
 * @date: 2024.01.22
 * @problem: BZOJ2226
 * @algo: 莫比乌斯函数
 */

#include<bits/stdc++.h>
using namespace std;

bool vis[1000001];
int cntPrime,prime[1000001];
long long f[1000001];

void precalc(int n=1000000){
    f[1]=1;
    for(int i=2;i<=n;i++){
        if(!vis[i])prime[++cntPrime]=i,f[i]=1+i*(i-1ll);
        for(int j=1;j<=cntPrime&&i*prime[j]<=n;j++){
            vis[i*prime[j]]=true;
            if(i%prime[j]==0){
                f[i*prime[j]]=f[i]+(f[i]-f[i/prime[j]])*prime[j]*prime[j];
                break;
            }
            f[i*prime[j]]=f[i]*f[prime[j]];
        }
    }
}

int main(){
    precalc();
    int T; scanf("%d",&T);
    while(T--){
        int n;
        scanf("%d",&n);
        printf("%lld\n",(f[n]+1)*n/2);
    }
    return 0;
}