数论题不多BB，直接开始推导吧：

\(\sum_{i=1}^n \sum_{j=1}^n \phi(gcd(i,j))\)

\(=\sum_{i=1}^n \sum_{j=1}^n \sum_{d=1}^n [gcd(i,j)=d]\phi(d)\)

\(=\sum_{d=1}^n \phi(d)\cdot(\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor} \sum_{j=1}^{\lfloor\frac{n}{d}\rfloor} [gcd(i,j)=1])\)

然后\(\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor} \sum_{j=1}^{\lfloor\frac{n}{d}\rfloor} [gcd(i,j)=1]=2\cdot\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor} \phi(i) -1\)，这个也是一个比较常用的结论了吧。具体可以看Luogu P2568 GCD的推导，之后为了方便，我们记\(sum_x=\sum_{i=1}^x \phi(i)\)

则上式\(=\sum_{d=1}^n(\phi(d)\cdot (2\cdot sum_{\lfloor\frac{n}{d}\rfloor}-1))\)

\(=2\cdot \sum_{d=1}^n(\phi(d)\cdot sum_{\lfloor\frac{n}{d}\rfloor})-sum_n\)

接下来就好做了，我们先把欧拉函数求前缀和，然后对于询问除法分块处理不同的\(sum_{\lfloor\frac{n}{d}\rfloor}\)即可。

复杂度\(O(n+T\sqrt n)\)，轻松跑过

CODE

#include<cstdio>

#define RI register int

using namespace std;

const int P=1e7;

int prime[P+5],phi[P+5],cnt,n,t; long long ans,sum[P+5]; bool vis[P+5];

inline void resolve(void)

{

    vis[1]=sum[1]=phi[1]=1; for (RI i=2;i<=P;++i)

    {

        if (!vis[i]) prime[++cnt]=i,phi[i]=i-1;

        for (RI j=1;j<=cnt&&i*prime[j]<=P;++j)

        {

            vis[i*prime[j]]=1; if (i%prime[j]) phi[i*prime[j]]=phi[i]*(prime[j]-1);

            else { phi[i*prime[j]]=phi[i]*prime[j]; break; }

        }

        sum[i]=sum[i-1]+phi[i];

    }

}

int main()

{

    for (scanf("%d",&t),resolve();t;--t)

    {

        scanf("%d",&n); ans=0; RI i,l,r;

        for (l=1;l<=n;l=r+1) r=n/(n/l),ans+=sum[n/l]*(sum[r]-sum[l-1]);

        printf("%lld\n",(ans<<1)-sum[n]);

    }

    return 0;

}