#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];
ll n;
ll dfs(ll now,ll v,int i){
	if(i>pt||now>n/p[i]/p[i])return ml(v,sum(n/now));
	ll res=0;
	for(int j=0;now<=n;now*=p[i],j++)
	(res+=j!=1?dfs(now,ml(v,h[i][j]),i+1):0)%=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++){
		h[i]={1};
		ll n=1,v=1;
		for(int j=1;(n*=p[i])<=mxn;j++)
		v=ml(v,p[i]),h[i]+=(ml(n,inv(j))+mod-v)%mod,(v+=h[i][j])%=mod;
	}
	int T;
	for(cin>>T;T--;)cin>>n,cout<<ml(dfs(1,1,1),inv(n))<<endl;
	return 0;
}