#include<bits/stdc++.h>
#define ll __int128
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
#define rev_rep(i,s,t) for(int i=(s);i>=(t);i--)
using namespace std;
int ci(){
	int x; scanf("%d",&x); return x;
}

enum{N=4000023};

const long long mod = (29ll<<57)+1;

int mindiv[N],prime[N]; int mu[N],phi[N];
//int k0[N],sig0[N]; ll pk[N],spk[N],sig[N];
int euler(int n){
	int tot = 0;
	mu[1] = phi[1] = 1;
//	sig0[1] = sig[1] = 1;
	rep(i,2,n){
		if( mindiv[i]==0 ){
			prime[mindiv[i]=++tot] = i;
			mu[i] = -1;
			phi[i] = i-1;
//			k0[i] = 1, sig0[i] = 2;
//			pk[i] = spk[i] = i, sig[i] = i+1;
		}
		rep(j,1,mindiv[i]){
			int x = i*prime[j];
			if( x>n ) break;
			mindiv[x] = j;
			mu[x] = j==mindiv[i] ? 0:-mu[i] ;
			phi[x] = j==mindiv[i] ? phi[i]*prime[j]:phi[i]*(prime[j]-1);
//			k0[x] = j==mindiv[i] ? k0[i]+1:1 ;
//			sig0[x] = j==mindiv[i] ? sig0[i]/k0[x]*(k0[x]+1):sig0[i]*2 ;
//			pk[x] = j==mindiv[i] ? pk[i]*prime[j]:prime[j] ;
//			spk[x] = j==mindiv[i] ? spk[i]+pk[x]:pk[x]+1 ;
//			sig[x] = j==mindiv[i] ? sig[i]/spk[i]*spk[x]:sig[i]*spk[x] ;
		}
	} return tot;
}

ll qpow(ll a,ll b){
	ll ans = 1;
	for(; b; b>>=1,a=a*a%mod) if( b&1 ){
		ans = ans*a%mod;
	} return ans;
}
ll inv(ll x){ return qpow(x,mod-2); }

ll Inv[N];
void init_inv(int n){
	Inv[1] = 1;
	rep(i,2,n) Inv[i] = (-(mod/i)*Inv[mod%i]%mod+mod)%mod;
}
/*
$$\begin{aligned}
p\bmod i &= p-\lfloor\frac{p}{i}\rfloor\cdot i\\
p\bmod i &\equiv -\lfloor\frac{p}{i}\rfloor\cdot i &\pmod p\\
i^{-1} &\equiv -\lfloor\frac{p}{i}\rfloor\cdot (p\bmod i)^{-1} &\pmod p
\end{aligned}$$
*/

struct ID{
	int id1[N],id2[N];
	ll n,block;
	void init(ll n0){ n=n0; block=sqrt((long long)n); }
	int& operator[](ll x){ return x<block ? id1[x]:id2[n/x]; }
}id;
ll num[N]; int tot; // 2*\sqrt{n}
ll g1[N];
const ll inv2 = inv(2);
const ll inv6 = inv(6);
#define s1(p) ((p)*(p+1)%mod*inv2%mod)
#define f1(p) (p)
#define f(pe,e) (f1(pe)*Inv[e]%mod)
void init_g(ll n){
	id.init(n);
	tot = euler(sqrt((long long)n));
	int m = 0;
	for(ll l=1,r; l<=n&&(r=n/(n/l)); l=r+1){
		ll x = n/l;
		num[id[x]=++m] = x;
		x %= mod;
		g1[m] = (s1(x)-1)%mod;
	}
	//rep(i,1,m) printf("(%lld) ", (long long)g1[i]); puts("");
	rep(j,1,tot){
		rep(i,1,m){
			ll x=num[i], y=x/prime[j];
			if( prime[j]>y ) break;
			g1[i] = (g1[i]-f1(1ll*prime[j])*(g1[id[y]]-g1[id[prime[j-1]]]))%mod;
		}
	}
	//rep(i,1,m) printf("(%lld) ", (long long)g1[i]); puts("");
	//rep(i,1,m) printf("(%lld,%lld) ", num[i], (long long)g1[i]); puts("");
}
ll Min_25(ll n,int j){
	if( prime[j]>n ) return 0;
		//printf("line %d: %lld %d\n", __LINE__, (long long)n, j);
	ll ans = ((g1[id[n]])-(g1[id[prime[j]]]))%mod;
	rep(k,j+1,tot){
		ll p = prime[k]; int e = 1;
		if( p*p>n ) break;
		for(ll pe=p; pe<=n; pe*=p,e++){
			ll x = pe%mod;
			ans = (ans+f(x,e)*(Min_25(n/pe,k)+(e!=1)))%mod;
		}
	}
		//printf("line %d: %lld %d = %lld\n", __LINE__, (long long)n, j, (long long)ans);
	return ans;
}
#undef s1
#undef f1
#undef f
/*
设$g(n,j)=\sum_{i=1}^nf_*(i)[i\in\mathbf{Primes}\text{ or mindiv}(i)>p_j]$

$$g(n,j)=g(n,j-1)-f_*(p_j)\left(g\left(\left\lfloor\frac{n}{p_j}\right\rfloor,j-1\right)-g(p_{j-1},j-1)\right)$$

$g(x,0)=\sum_{i=2}^{x}f_*(i),\ x=\lfloor\frac{n}{a}\rfloor\quad\Rightarrow\quad g(x)=g(x,\pi(x))=\sum_{i\le x} f_*(i)[i\in\mathbf{Primes}]$

设$S(n,j)=\sum_{i=1}^nf(i)[\text{mindiv}(i)>p_j]$

$$S(n,j)=g(n)-g(p_j)+\sum_{j<k,p_k\le \sqrt n,1\le e,p_k^e\le n} f(p_k^e)\left(S\left(\left\lfloor\frac{n}{p_k^e}\right\rfloor,k\right)+[e\neq 1]\right)$$

$S(n,j)=0,\ p_j>n \quad\Rightarrow\quad S(n,0)=\sum_{i=2}^nf(i)$
*/

signed main(){
	int T = ci();
	init_inv(1000);
	while( T-- ){
		long long n;
		cin>>n;
		init_g(n);
		cout<<(long long)(((Min_25(n,0)+1)*inv(n)%mod+mod)%mod)%mod<<endl;
	}
	return 0;
}