#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(abs(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();
    }
}

answer.code: In function ‘void calc(__int128, __int128, __int128)’:
answer.code:26:40: error: call of overloaded ‘abs(__int128&)’ is ambiguous
   26 |             ans+=(h>0?1:-1)*now*Pow(abs(h),Mod-2)%Mod*(M/now)%Mod*(M/now+1)*Pow(2,Mod-2)%Mod;
      |                                     ~~~^~~
In file included from /usr/include/c++/11/bits/std_abs.h:38,
                 from /usr/include/c++/11/cmath:47,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from answer.code:1:
/usr/include/stdlib.h:840:12: note: candidate: ‘int abs(int)’
  840 | extern int abs (int __x) __THROW __attribute__ ((__const__)) __wur;
      |            ^~~
In file included from /usr/include/c++/11/cmath:47,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from answer.code:1:
/usr/include/c++/11/bits/std_abs.h:79:3: note: candidate: ‘constexpr long double std::abs(long double)’
   79 |   abs(long double __x)
      |   ^~~
/usr/include/c++/11/bits/std_abs.h:75:3: note: candidate: ‘constexpr float std::abs(float)’
   75 |   abs(float __x)
      |   ^~~
/usr/include/c++/11/bits/std_abs.h:71:3: note: candidate: ‘constexpr double std::abs(double)’
   71 |   abs(double __x)
      |   ^~~
/usr/include/c++/11/bits/std_abs.h:61:3: note: candidate: ‘long long int std::abs(long long int)’
   61 |   abs(long long __x) { return __builtin_llabs (__x); }
      |   ^~~
/usr/include/c++/11/bits/std_abs.h:56:3: note: candidate: ‘long int std::abs(long int)’
   56 |   abs(long __i) { return __builtin_labs(__i); }
      |   ^~~