#include<bits/stdc++.h>
using LL = long long;
using LLL = __int128;
constexpr LL mod = 29LL << 57 | 1LL;
constexpr LL M(LL a, LL b) {
	a %= mod, b %= mod;
	return LLL(a) * LLL(b) % mod;
}
constexpr LL J(LL a, LL b) {
	a %= mod, b %= mod;
	return a >= b ? a - b : mod - b + a; 
}
constexpr LL qpow(LL a, LL b) {
	LL v = 1;
	for (; b; b >>= 1, a = M(a, a))
		if (b & 1) v = M(v, a);
	return v;
}
constexpr LL inv2 = qpow(2LL, mod - 2);
const int maxm = 1e6;
const LL maxn = LL(1e12);
std::unordered_map<LL, LL> h; 
int m;
int p[maxm + 1];
LL n;
LL ans;
void dfs(int w, LL x, LL v) {
	if (w > m || x * p[w] > n || x * p[w] * p[w] > n) {
		ans = (ans + M(v, M(M(n / x, n / x + 1), inv2))) % mod;
		return ;
	}
	dfs(w + 1, x, v);
	x *= p[w] * p[w];
	while(true) {
		dfs(w + 1, x, M(v, h[x]));
		if ((x *= p[w]) > n) break;
	}
}
std::bitset<maxm + 1> vis;
LL stp[100];
int main() {
	h[1] = 1LL;
	for (int i = 2; i <= maxm; i++) {
		if (! vis[i]) {
			p[++m] = i;
			h[i] = 0;
			LL x = 1LL * i * i;
			int c = 1;
			stp[0] = 1, stp[1] = i; 
			for (int j = 2; x <= maxn; j++, x *= i) {
				LL v = M(x, qpow(j, mod - 2));
				LL P = i;
				for (int k = j - 1; ~ k; k--, P = M(P, i)) v = J(v, M(P, h[stp[k]]));
				stp[++c] = x, h[x] = v;
			} 
		}
		for (int j = 1; j <= m && i * p[j] <= maxm; j++) {
			vis[i * p[j]] = 1;
			if (i % p[j] == 0) break;
		}
	}
	int T;
	scanf("%d", &T);
	for (; T; T--) {
		scanf("%lld", &n);
		ans = 0;
		dfs(1, 1LL, 1LL);
		printf("%lld\n", M(ans, qpow(n, mod - 2)));
	}
	return 0;
}