给出一个数字N

#include<bits/stdc++.h>

#define maxn 10000003

#define M 10000000

#define ll long long

using namespace std;

void setIO(string s)

{

	string in=s+".in";

	freopen(in.c_str(),"r",stdin);

}

int cnt;

bool vis[maxn];

int prime[maxn], phi[maxn];

ll sumv[maxn];

inline void Linear_shaker()

{

	phi[1]=1;

	int i,j;

	for(i=2;i<=M;++i)

	{

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

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

		{

			vis[i*prime[j]]=1;

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

			{

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

				break;

			}

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

		}

	}

	for(i=1;i<=M;++i) sumv[i]=sumv[i-1]+phi[i];

}

inline void solve()

{

	int n,i,j;

	scanf("%d",&n);

	ll re=0;

	for(i=1;i<=n;i=j+1)

	{

		j=(n/(n/i));

		re+=(sumv[j]-sumv[i-1])*(sumv[n/i]*2-1);

	}

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

}

int main()

{

	// setIO("input");

	Linear_shaker();

	int T;

	scanf("%d",&T);

	while(T--) solve();

	return 0;

}