#include <bits/stdc++.h>
const int N = 2e6 + 10;
using namespace std;
#define ll __int128_t
#define lll long long
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;
}
lll isp[N], p[N], tot;
lll M;
ll ans = 0,inv2;
lll inv[100];
struct node
{
    /* data */
    lll now, pos, h;
};

void calc()
{

    stack<node> st;
    st.push((node){1, 0, 1});
    while (!st.empty())
    {
        node tmp=st.top();
        st.pop();
        lll now=tmp.now,pos=tmp.pos,h=tmp.h;
        
        // printf("%lld %lld %lld\n",(long long) pos,(long long) M,(long long) p[pos]*p[pos]);
        if (p[pos] * p[pos] > M / now)
        {
            if (now == 1)
            {
                ans += (M * (M - 1)%Mod *inv2) % Mod;
            }
            else
            {

                ans += now * h % Mod * (M / now) % Mod * (M / now + 1) * inv2 % 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);
            continue;
        }
        // calc(now, pos + 1, h);
        // if (p[pos] * p[pos] > M / now)continue;
        st.push((node){now, pos + 1, h});
        // if(p[pos]==0)
        // {
        //     printf("%lld"p[pos-1]);
        // }
        for (lll i = 2, pj = p[pos] * p[pos]; now <= M / pj; i++, pj *= p[pos])
        {
            // calc(now * pj, pos + 1, h * (-i * (i - 1)));  
            st.push((node){now * pj, pos + 1, h * inv[i]%(lll)Mod});
        }
    }
}
void solve()
{
    long long _;
    cin >> _;
    M = _;
    calc();
    ans = ans * inv2 % Mod;
    printf("%lld\n", (long long)ans);
}
int main()
{
    inv2=Pow(2,Mod-2);
    for(int i=1;i<100;i++)inv[i]=-Pow(i*(i-1),Mod-2);
    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();
    }
}
/*
12
4
959139
9859
125987
209411
965585325539
213058376259
451941492387
690824608515
934002691939
1000000000000
1
*/