#include<cstring>

 #include<cmath>

 #include<iostream>

 #include<algorithm>

 #include<cstdio>

 #define ll long long

 #define N 10000007

 using namespace std;

 inline int read()

 {

     int x=,f=;char ch=getchar();

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

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

     return x*f;

 }

 int n;

 int cnt,pri[N],phi[N];

 ll sum[N];

 bool flag[N];

 void init_phi()

 {

     phi[]=;

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

     {

         if (!flag[i])pri[++cnt]=i,phi[i]=i-;

         for (int j=;j<=cnt&&pri[j]*i<=;j++)

         {

             flag[pri[j]*i]=;

             if (i%pri[j]==)

             {

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

                 break;

             }

             else phi[pri[j]*i]=phi[i]*phi[pri[j]];

         }

     }

     for (int i=;i<=;i++)sum[i]=sum[i-]+phi[i];

 }

 void solve(ll n)

 {

     ll last,ans=;

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

     {

         last=n/(n/i);//琛ㄧずn涓埌杈惧摢閲屼负姝㈤兘鏄痭/i鐨?

         ans+=(sum[last]-sum[i-])*((sum[n/i]<<)-);

     }

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

 }

 int main()

 {

     init_phi();

     int T=read();

     while(T--)

     {

         n=read();

         solve(n);

     }

 }