#include<bits/stdc++.h>
const int N=1e6+10;
using namespace std;
#define ll __int128_t
const ll Mod=(1ll<<57)*29ll+1;
ll Pow(ll n, ll k)
{
    ll res=1;
    for(ll x=n;k;x=x*x%Mod,k>>=1)if(k&1)res=res*x%Mod;
    return res;
}
int isp[N],p[N],tot;
ll M;
ll ans=0;
void calc(ll now,ll pos,ll h)
{
    if(p[pos]*p[pos]>M/now)
    {
        if(now==1)
        {
            ans+=(M*(M-1)/2)%Mod;
        }
        else
        {
            
            ans+=(h>0?1:-1)*now*Pow((h>0?h:-h),Mod-2)%Mod*(M/now)%Mod*(M/now+1)*Pow(2,Mod-2)%Mod;
            ans=(ans%Mod+Mod)%Mod;
            // printf("%lld %lld\n",(long long)now,(long long)(h>0?1:-1)*now*Pow(abs(h),Mod-2)%Mod);
        }
        // printf("%lld\n",(long long)ans);
        return;
    }
    calc(now,pos+1,h);
    for(int i=2,pj=p[pos]*p[pos];now<=M/pj;i++,pj*=p[pos])
    {
        calc(now*pj,pos+1,h*(-i*(i-1)));
    }
}
void solve()
{
    long long _;
    cin>>_;
    M=_;
    calc(1,0,1);
    ans=ans*Pow(2,Mod-2)%Mod;
    printf("%lld\n",(long long)ans);
}
int main()
{
    for (int i = 2; i <= N - 10; i++)
    {
        if (!isp[i])
            p[tot++] = i;
        for (int j = 0; i * p[j] < N && j < tot; j++)
        {
            isp[i * p[j]] = 1;
            if (i % p[j])
                ;
            else
                break;
        }
    }
    int T;
    cin>>T;
    while(T--)
    {
        solve();
    }
}