#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 2e6 + 50;
const ll MOD = 4179340454199820289ll;

ll fpow (ll x, ll p) {
    ll res = 1;
    for (; p; p >>= 1, x = (__int128)x * x % MOD)
        if (p & 1) res = (__int128)res * x % MOD;
    return res;
}

const ll inv2 = fpow (2, MOD - 2);
const ll inv3 = fpow (3, MOD - 2);

ll n, w[N], inv[N];
ll p[N], sp1[N], tp, sqrn;
bool isp[N];

void get_p (int m) {
    isp[1] = 1;
    for (int i = 2; i <= m; i ++) {
        if (! isp[i]) p[++ tp] = i;
        for (int j = 1; j <= tp && i * p[j] <= m; j ++) {
            isp[i * p[j]] = true;
            if (i % p[j] == 0) break;
        }
    }
    for (int i = 1; i <= tp; i ++) sp1[i] = (sp1[i - 1] + p[i]) % MOD;
    inv[1] = 1;
    for (int i = 2; i < N; i ++) 
        inv[i] = inv [MOD % i] * (__int128)(MOD - MOD / i) % MOD;
}

ll ind1[N], ind2[N], tot, g1[N], g2[N];
ll S (ll x, ll y) {
    if (p[y] >= x) return 0;
    int k = x <= sqrn ? ind1[x] : ind2[n / x];
    ll ans = ((__int128)g1[k] - sp1[y] + MOD) % MOD;
    for (int i = y + 1; i <= tp && (ll)p[i] * p[i] <= x; ++ i) {
        __int128 pe = p[i];
        for (ll e = 1; pe <= x; ++ e, pe *= p[i]) {
            ll xx = pe % MOD;
            ans = (ans + (__int128)xx * inv[e] % MOD * (S (x / pe, i) + (e > 1)) % MOD) % MOD;
        }
    }
    return ans;
}

int T = 1; 

void solve () {
    scanf ("%lld", &n);
    if (n > N) { printf("0\n"); return ; }
    tot = 0;
    sqrn = sqrt (n);
    for (ll l = 1, r, tn; l <= n; l = r + 1) {
        r = n / (n / l), w[++ tot] = n / l, tn = w[tot] % MOD;
        g1[tot] = (__int128)tn * (tn + 1) % MOD * inv2 % MOD - 1;
        if (w[tot] <= sqrn) ind1[w[tot]] = tot;
        else ind2[n / w[tot]] = tot;
    }
    for (int i = 1; i <= tp; i ++) {
        for (int j = 1; j <= tot && (__int128)p[i] * p[i] <= w[j]; j ++) {
            int k = (w[j] / p[i]) <= sqrn ? ind1[w[j] / p[i]] : ind2[n / (w[j] / p[i])];
            (g1[j] -= (__int128)p[i] * (g1[k] - sp1[i - 1] + MOD) % MOD) %= MOD;
            (g1[j] += MOD) %= MOD;
        }
    }
    ll ans = (__int128)(S (n, 0) + 1) * fpow (n, MOD - 2) % MOD;
    printf("%lld\n", ans);
}

int main() {
#ifdef LOCAL
    clock_t c1 = clock();
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    // ===================================================    
    // cerr << (MOD + MOD) << endl;
    get_p (N - 1);
    scanf ("%d", &T);
    while (T --) {
        solve ();
    }
    // ===================================================    
#ifdef LOCAL
    cerr << "Time Used: " << clock() - c1 << "ms" << endl;
#endif
    return 0;
}