#include <bits/stdc++.h>
typedef long long LL;
typedef __int128 LLL;
typedef unsigned long long ULL;
typedef __uint128_t ULLL;
typedef std::pair<int, int> pii;
typedef std::pair<int, LL> pil;
typedef std::pair<LL, int> pli;
typedef std::pair<LL, LL> pll;
#define MP std::make_pair
#define fi first
#define se second

bool M1;
char buf[1 << 20], *p1 = 0, *p2 = 0; 
#define getchar() ((p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), (p1 == p2))) ? 0 : *p1++)
LL read()
{
	LL s = 0; int f = 1, c = getchar();
	for (; !isdigit(c); c = getchar()) f ^= (c == '-');
	for (; isdigit(c); c = getchar()) s = s * 10 + (c ^ 48);
	return f ? s : -s;
}
template<typename T> void write(T x, char end = '\n')
{
	if (x < 0) putchar('-'), x = -x;
	static int d[100], cur = 0;
	do { d[++cur] = x % 10; } while (x /= 10);
	while (cur) putchar('0' + d[cur--]);
	putchar(end);
}
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3fll;
template<typename T> void Fmax(T& x, T y){ if (x < y) x = y; }
template<typename T> void Fmin(T& x, T y){ if (y < x) x = y; }
const LL MOD = (29ll << 57) + 1;
LL fplus(LL x, LL y){ return x + y >= MOD ? x + y - MOD : x + y; }
LL fminus(LL x, LL y){ return x >= y ? x - y : x + MOD - y; }
void Fplus(LL &x, LL y){ x = fplus(x, y); }
void Fminus(LL &x, LL y){ x = fminus(x, y); }
LL fpow(LL x, LL y = MOD - 2)
{
	LL res = 1; 
	for (; y; x = (LLL)x * x % MOD, y >>= 1)
		if (y & 1) res = (LLL)res * x % MOD;
	return res;	
}
const int MAXN = 2000005; 
const int B = 1000000;
const LL LIM = 1e12;
const LL inv[]={0, 1, 2089670227099910145, 1393113484733273430, 3134505340649865217, 835868090839964058, 696556742366636715, 1791145908942780124, 3656922897424842753, 464371161577757810, 417934045419982029, 3419460371618034782, 2437948598283228502, 1285950908984560089, 895572954471390062, 278622696946654686, 3918131675812331521, 491687112258802387, 232185580788878905, 3299479305947226544, 2298637249809901159, 1990162121047533471, 1709730185809017391, 1998814999834696660, 1218974299141614251, 2674777890687884985, 2732645681592190189, 2941017356659132796, 447786477235695031, 4035225266123964417, 139311348473327343, 1213356906058012342, 4048736065006075905, 3926047093339225120, 2335513783229311338, 3701701545148412256, 2205763017494349597, 3727519864556596474, 1649739652973613272, 428650302994853363, 3238988852004860724, 203870266058527819, 3084751287623676880, 777551712409268891, 2944535320004418840, 92874232315551562, 999407499917348330, 1956287021114809497, 2699157376670717270, 255877986991825732, 3427059172443852637, 1557009188819540892, 3455993067896005239, 1340543164554659338, 1470508678329566398, 2355628256003535072, 2313563465717757660, 2492939920049015611, 4107282860161892353, 2691778597620223237, 2159325901336573816, 2809064895445780850, 606678453029006171, 663387373682511157, 4114038259602948097, 3600662545156768249, 1963023546669612560, 2807019708044655418, 1167756891614655669, 2059385151344838983, 1850850772574206128, 941823200946438375, 3192551735847084943, 1488532216564319555, 1863759932278298237, 891592630229294995, 824869826486806636, 1682591611431096480, 2303995378597336826, 2380636967582176114, 1619494426002430362, 3766566088352924458, 2191605360129174054, 1863079479583052418, 1542375643811838440, 1770073604131688593, 2478446083304544590, 1345075088707988139, 1472267660002209420, 2535779601424610063, 46437116157775781};
int pr[MAXN], cP, m, tot, id[MAXN], cPN;
pll pn[MAXN << 1];
bool isP[MAXN];
std::vector<LL> h[80005];
LL n;
void Euler(int n)
{
	memset(isP + 1, true, n), isP[1] = false;
	for (int i = 2; i <= n; i++)
	{
		if (isP[i]) pr[++cP] = i;
		for (int j = 1; pr[j] <= n / i; j++)
		{
			isP[pr[j] * i] = false;
			if (i % pr[j] == 0) break;
		}
	}
}
void initH()
{
	for (int i = 1; i <= cP; i++)
	{
		h[i].push_back(1), h[i].push_back(0);
		for (LL P = (LL)pr[i] * pr[i], k = 2; P <= LIM; P *= pr[i], k++)
		{
			LL sum = (LLL)P * inv[k] % MOD, v = P;
			for (int c = 0; c < k; c++, v /= pr[i])
				Fminus(sum, (LLL)v * h[i][c] % MOD);
			h[i].push_back(sum);
		}
	}
}
void dfs(LL num, int x, LL val)
{
	pn[++cPN] = MP(num, val);
	for (int i = x + 1; i <= cP && (LL)pr[i] * pr[i] <= LIM / num; i++)
		for (LL P = (LL)pr[i] * pr[i], k = 2; P <= LIM / num; P *= pr[i], k++)
			assert(k < h[i].size()), dfs(num * P, i, (LLL)val * h[i][k] % MOD);
}
LL linS(LL x){ return (LLL)x * (x + 1) / 2 % MOD; }
void mian()
{
	n = read();
	LL ans = 0;
	for (int i = 1; i <= cPN; i++)
		if (pn[i].fi <= n) ans = (ans + (LLL)pn[i].se * linS(n / pn[i].fi)) % MOD;
	ans = (LLL)ans * fpow(n) % MOD, write(ans);
}
int main()
{ 
//	freopen("1.in", "r", stdin);
	Euler(1000000);
	initH();
	dfs(1, 0, 1);
	for (int Tcnt = read(); Tcnt--; ) mian();
	return 0;
}