#include<bits/stdc++.h>
using namespace std;
namespace Poll{
    #define ll long long
    #define mytz __builtin_ctzll
    inline ll multi(ll &a,ll &b,ll &m){
        __int128 X=a,Y=b,Z=m;
        X=X*Y%Z;
        return X;
    }
    inline ll Irand(ll x){
        return 1ull*((rand()<<15^rand())<<30^(rand()<<15^rand()))%x; //2
    }
    ll KSM(ll a,ll b,ll m){
        ll ans=1LL;
        while(b){
            if(b&1)ans=multi(ans,a,m);
            b>>=1;
            a=multi(a,a,m);
        }
        return ans;
    }
    bool mr(ll x,ll b){
        ll k=x-1;
        while(k){
            ll cur=KSM(b,k,x);
            if(cur!=1&&cur!=x-1)return false;
            if((k&1)==1||cur==x-1)return true;
            k>>=1;
        }
        return true;
    }
    bool prime(ll x){
        if(x==46856248255981ll||x<2)return false;
        if(x==2||x==3||x==7||x==61||x==24251)return true;
        return mr(x,2)&&mr(x,61);
    }
    inline ll m_max(ll a,ll b){return a>b?a:b;}
    ll ans=0,c,mod;
    //inline ll f(ll x){return (multi(x,x,mod)+c)%mod;}
    inline ll gcd(ll a,ll b){
        if(!a)return b;
        if(!b)return a;
        register int t=mytz(a|b);
        a>>=mytz(a);
        do{
            b>>=mytz(b);
            if(a>b){ll t=b;b=a,a=t;}
            b-=a;
        }while(b);
        return a<<t;
    }
    inline ll m_abs(ll x){return x>0?x:-x;}
    // find(ll p){
    //	if(!(p&1))return 2LL;
    //	mod=p;
    //	register ll a,b,x;
    //	while(1){
    //		a=b=Irand(p-2)+1,c=Irand(p-2)+1;
    //		do{
    //			a=f(a);
    //			b=f(f(b));
    //			x=gcd(m_abs(a-b),p);
    //			if(x!=1 and x!=p)return x;
    //		}while(a!=b);
    //	}
    //	return p;
    //}
    ll f(ll x,ll c,ll n)
        {
            return ((__int128)x*x+c)%n;
        }
        ll find(ll x)
        {
            ll s=0,t=0,c=1ll*rand()%(x-1)+1,val=1;
            for(int gol=1;;gol<<=1,s=t,val=1)
            {
                for(int i=1;i<=gol;++i)
                {
                    t=f(t,c,x);
                    val=(__int128)val*abs(t-s)%x;
                    if((i&127)==0)
                    {
                        ll d=gcd(val,x);
                        if(d>1)return d;
                    }
                }
                ll d=gcd(val,x);
                if(d>1)return d;
            }
        }
    long long D(ll x){
        vector<ll>p;p.clear();
        if(x==1)return 1;
        register ll u;
        while(!prime(x)&&x>1){
            u=find(x);
            while(u==x||!prime(u))u=find(u);
            while(x%u==0){
                x/=u;
                p.push_back(u);
            }
        }
        if(x!=1)p.push_back(x);
        sort(p.begin(), p.end());
        int i,num=2;
        long long res=1;
        for(i=1;i<p.size();++i){
            if(p[i]!=p[i-1]){
                res*=num;
                num=2;
            }
            else ++num;
        }
        return res*num;
    }
}
int id1[317000], id2[317000];
long long n,sq;
int get_id(int x){
    if(x<=sq)return id1[x];
    else return id2[n/x];
}
short Smu[635000];
long long Sf2[635000];
void work(){
    long long L,R,num;
    scanf("%lld",&n);
    sq=sqrtl(n);
    int cnt=0;
    for(L=1;L<=n;L=(R+1)){
        R=n/(n/L);
        cnt++;
        num=n/R;
        if(num<=sq)id1[num]=cnt;
        else id2[n/num]=cnt;
    }
    //Smu[get_id(1)]=1;
    for(R=n;R>=1;R=L-1){
        long long tmp = n/R + 1;
        if(n % tmp == 0)L = n/tmp+1;
        else L = (n+tmp-1)/tmp;
        num = n/R;
        long long l1,r1;
        long long ans=1;
        for(l1=2;l1<=num;l1=r1+1){
            r1=num/(num/l1);
            ans -= 1LL*Smu[get_id(num/r1)]*(r1-l1+1);
        }
        Smu[get_id(num)]=ans;
    }
    for(R=n;R>=1;R=L-1){
        long long tmp=n/R+1;
        if(n % tmp == 0)L = n/tmp+1;
        else L = (n+tmp-1)/tmp;
        num = n/R;
        long long l1,r1;
        long long ans=num;
        for(l1=2;l1<=num;l1=r1+1){
            r1=num/(num/l1);
            ans -= 1LL*Sf2[get_id(num/r1)]*(Smu[get_id(r1)]-Smu[get_id(l1-1)]);
        }
        Sf2[get_id(num)]=ans;
    }
    long long Ans=0;
    for(L=1;L<=n;L=R+1){
        R=n/(n/L);
        //printf("%lld %lld %lld\n",R, Smu[get_id(R)], Sf2[get_id(R)]);
        Ans -= Poll::D(n/R)*(R-L+1);
        Ans += (n/R)*(Sf2[get_id(R)] - Sf2[get_id(L-1)]);
    }
    printf("%lld\n",Ans);
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        work();
    }
    return 0;
}