#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 + a - b; 
}
constexpr LL qpow(LL a, LL b) {
	a %= mod;
	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, maxp = 78948;
const LL maxn = LL(1e12);
int m;
int p[maxm + 1];
LL h[maxp + 1][42];
LL n;
LL ans;
void dfs(int w, LL x, LL v) {
	printf("%d %lld\n", w, x);
	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 *= 1LL * p[w] * p[w];
	for (int i = 2; x <= n; x *= p[w], i++) dfs(w + 1, x, M(v, h[w][i]));
}
std::bitset<maxm + 1> vis;
LL inv[42];
int main() {
	inv[1] = 1LL;
	for (int i = 2; i < 42; i++) inv[i] = M(mod - mod / i, inv[mod % i]);
	for (int i = 2; i <= maxm; i++) {
		if (! vis[i]) {
			p[++m] = i;
			h[m][0] = 1LL, h[m][1] = 0LL;
			LL x = 1LL * i * i;
			LL fv = M(x, inv2), ghv = x;
			for (int j = 2; x <= maxn; j++, x *= i) {
				h[m][j] = J(fv, ghv), fv = M(fv, M(M(j, i), inv[j + 1])), ghv = M((ghv + h[m][j]) % mod, i) % mod;
			} 
		}
		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;
}