#include <cstdio>
#include <cstring>
#include <cassert>
#include <algorithm>
#include <queue>
#include <map>
#define fi first
#define se second
#define eb emplace_back
#define ep emplace
using namespace std;
typedef long long LL;
typedef __int128 LLL;

template <typename Tp> void read(Tp& x) {
    char ch; bool op = 0; x = 0;
    do ch = getchar(), op |= ch == '-'; while (ch < '0' || ch > '9');
    do x = (x<<3)+(x<<1)+(ch&15), ch = getchar(); while (ch >= '0' && ch <= '9');
    if (op) x = -x;
}

const LL mod = 4179340454199820289;
inline LL fplus(LL x, LL y) { return x + y >= mod ? x + y - mod : x + y; }
inline LL Fplus(LL& x, LL y) { return x = fplus(x, y); }
inline LL fminus(LL x, LL y) { return x - y < 0 ? x - y + mod : x - y; }
inline LL Fminus(LL& x, LL y) { return x = fminus(x, y); }
LL qpow(LL x, LL y = mod - 2) {
    LL res = 1;
    if (x >= mod) x %= mod;
    for (; y; y >>= 1, x = (LLL)x * x % mod) if (y & 1) res = (LLL)res * x % mod;
    return res;
}
const int MAXN = 1e6+5;
LL N; 
int pri[MAXN], v[MAXN], cnt;
void sieve(int n) {
    for (int i = 2; i <= n; ++i) {
        if (!v[i]) v[i] = pri[++cnt] = i;
        for (int j = 1; j <= cnt && pri[j] <= n / i; ++j) {
            v[i*pri[j]] = v[i];
            if (v[i] == pri[j]) break;
        }
    }
}
LL inv[105];
LL sum;
inline LL S(LL n) { return (LLL) n * (n + 1) / 2 % mod; }
inline LL H_p2(LL p) { return mod - (LLL)p * p * inv[2] % mod; }
vector<pair<LL, LL> > num;
void solve(int x, LL mul, LL H, int c) {
    static const LL V = 1e12;
    num.eb(mul, H);
    if (pri[x] <= V / mul) solve(x, mul * pri[x], (LLL)H*inv[c+1]%mod*(c-1)*pri[x]%mod, c + 1);
    for (int y = x + 1; y <= cnt; ++y) {
        LL sq = (LL)pri[y] * pri[y];
        if (sq > V / mul) break;
        solve(y, mul * sq, (LLL)H * H_p2(pri[y]) % mod, 2);
    }
}

int main() {
    #ifndef ONLINE_JUDGE
    assert(freopen("qoj4478.in", "r", stdin));
    assert(freopen("qoj4478.out", "w", stdout));
    #endif
    int T; read(T);
    fprintf(stderr, "%lld\n", fminus(0, (LLL)64 * qpow(9) % mod));
    sieve(1e6);
    inv[1] = 1;
    for (int i = 2; i <= 100; ++i) inv[i] = (LLL)(mod - mod / i) * inv[mod % i] % mod;
    num.eb(1, 1);
    for (int i = 1; i <= cnt; ++i) {
        LL sq = (LL)pri[i] * pri[i]; 
        assert(sq <= 1e12);
        solve(i, sq, H_p2(pri[i]), 2);
    }
    while (T--) {
        read(N); 
        sum = 0;
        for (auto pr : num) Fplus(sum, (LLL)pr.se * S(N / pr.fi) % mod);
        sum = (LLL) sum * qpow(N) % mod;
        printf("%lld\n", sum);
    }
    return 0;
}