#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using lll=__int128;
constexpr ll mod=29ll<<57|1,mxn=1e12;
constexpr int sqn=1e6;
auto ml=[](ll x,ll y)->ll{return(lll)x*y%mod;};
auto inv=[](ll p){ll res=1,t=mod-2;for(;t;t>>=1,p=ml(p,p))if(t&1)res=ml(res,p);return res;};
auto sum=[](ll n)->ll{return(lll)n*(n+1)/2%mod;};
int p[sqn+10],pt;
basic_string<ll>h[79010],pp[79010];
ll n;
ll dfs(ll now,ll v,int i){
	if(i>pt||now>n/pp[i][2])return ml(v,sum(n/now));
	ll res=dfs(now,v,i+1);
	for(int j=2;j<pp[i].size()&&now*pp[i][j]<=n;j++)
	(res+=dfs(now*pp[i][j],ml(v,h[i][j]),i+1))%=mod;
	return res;
}
int main(){
	for(int i=2;i<=sqn;i++)
	if(!p[i])for(int j=p[++pt]=i;j<=sqn;j+=i)p[j]=1;
	for(int i=1;i<=pt;i++){
		pp[i]=h[i]={1};
		ll now=1;
		for(int j=1;pp[i][j-1]*p[i]<=mxn;j++)
		now=ml(now,p[i]),pp[i]+=pp[i][j-1]*p[i],
		h[i]+=(ml(pp[i][j],inv(j))+mod-now)%mod,(now+=h[i][j])%=mod;
	}
	int T;
	for(cin>>T;T--;)cin>>n,cout<<ml((sum(n)+dfs(1,1,1))%mod,inv(n))<<endl;
	return 0;
}