#include<bits/stdc++.h>
using namespace std;
typedef long long LL; 
const int N=2e7+10;
int prime[N], pr, phi[N];
bool v[N];
LL F[N];
void get_phi()
{
	pr=0;phi[1]=0;//根据此题，phi[1]不适合等于1 
	memset(v,0,sizeof(v));
	for(int i=2;i<=20000000;i++)
	{
		if(v[i]==0)prime[++pr]=i,phi[i]=i-1;
		for(int j=1;(j<=pr)&&(i*prime[j]<=20000000);j++)
		{
			v[i*prime[j]]=1;
			if(i%prime[j]==0)
			{
				phi[i*prime[j]]=phi[i]*prime[j];
				break;
			}
			else 
			{
				phi[i*prime[j]]=phi[i]*phi[prime[j]]; 
			}
		}
	}
} 
int main()
{
    get_phi();
	int n;scanf("%d",&n);
    F[1]=0;for(int i=1;i<=20000000;i++) F[i]=F[i-1]+phi[i];
    while(n--)
    {
        int x;scanf("%d",&x);printf("%lld\n",F[x]);
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long LL; 
const int N=2e7+10;
int prime[N],pr,phi[N];
bool v[N];
LL F[N];
void get_phi()
{
	pr=0;phi[1]=0;//根据此题，phi[1]不适合等于1 
	memset(v,0,sizeof(v));
	for(int i=2;i<=20000000;i++)
	{
		if(v[i]==0)prime[++pr]=i,phi[i]=i-1;
		for(int j=1;(j<=pr)&&(i*prime[j]<=20000000);j++)
		{
			v[i*prime[j]]=1;
			if(i%prime[j]==0)
			{
				phi[i*prime[j]]=phi[i]*prime[j];
				break;
			}
			else 
			{
				phi[i*prime[j]]=phi[i]*phi[prime[j]]; 
			}
		}
	}
} 
int main()
{
    get_phi();
	int n;scanf("%d",&n);
    F[1]=0;for(int i=1;i<=20000000;i++) F[i]=F[i-1]+phi[i];
    while(n--)
    {
        int x;scanf("%d",&x);printf("%lld\n",F[x]);
    }
    return 0;
}