#include<bits/stdc++.h>

using namespace std;

const int N=2e6+;

typedef long long ll;

int n,cnt,prime[N],phi[N],mu[N],vis[N];

ll ans,s[N],f[N];

void calcmu(){

    memset(prime,,sizeof(prime));cnt=;

    memset(phi,,sizeof(phi));memset(mu,,sizeof(mu));

    memset(s,,sizeof(s));memset(f,,sizeof(f));

    mu[]=;phi[]=;memset(vis,,sizeof(vis));

    for(int i=;i<=n;i++){

        if(vis[i]){prime[++cnt]=i;mu[i]=-;phi[i]=i-;}

        for(int j=;j<=cnt;j++){

            int t=prime[j]*i;if(t>n)break;

            vis[t]=;

            if(i%prime[j]==){

                mu[t]=;phi[t]=phi[i]*prime[j];

                break;

            }

            mu[t]=-mu[i];phi[t]=phi[i]*(prime[j]-);

        }

    }

    for(int i=;i<=n;i++)s[phi[i]]++;

    for(int i=;i<=n;i++)

    for(int j=i;j<=n;j+=i)f[i]+=s[j];

    for(int i=;i<=n;i++)f[i]=f[i]*f[i];

    for(int i=;i<=n;i++)if(mu[i]!=)

    for(int d=;i*d<=n;d++)ans+=mu[i]*phi[d]*f[i*d];

    printf("%lld\n",ans);

}

inline int read(){

    int f=,x=;char ch;

    do{ch=getchar();if(ch=='-')f=-;}while(ch<''||ch>'');

    do{x=x*+ch-'';ch=getchar();}while(ch>=''&&ch<='');

    return f*x;

}

int main(){

    int T=read();

    while(T--){

        n=read();ans=;calcmu();

    }

}