#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector> 
#include <cmath>
#define int __int128_t
using namespace std;

const int md=4179340454199820289ll,N=1e12;
void read(int &x){
	x=0;
	int f=1;
	char c=getchar();
	while(!('0'<=c && c<='9')){
		if(c=='-'){
			f=-1;
		}
		c=getchar();
	}
	while('0'<=c && c<='9'){
		x=(x<<3)+(x<<1)+(c^48);
		c=getchar();
	}
}
__int128_t powr(__int128_t b,int k){
	__int128_t res=1;
	for(;k;k>>=1,b=b*b%md){
		if(k&1){
			res=res*b%md;
		}
	}
	return res;
}
int a[1000010],cnt=0,tp=0;
__int128_t act[5000010],*fp[2000010],inv[1000010];
bool p[1000010];
int pnc[10000010],val[10000010],pc=0;
void sieve(int n){
	for(int i=2;i<=n;i++){
		if(!p[i]){
			fp[i]=act+tp;
			fp[i][0]=1;
			tp++;
			a[++cnt]=i;
			for(int j=i,k=1;j<=N;j*=i,k++){
				fp[i][k]=j*inv[k]%md;
				tp++;
				for(int l=i,q=1;l<=j;l*=i,q++){
					fp[i][k]=(fp[i][k]+(md-fp[i][k-q])*l)%md;
				}
				//printf("[%lld %lld:%lld]",(long long)i,(long long)k,(long long)fp[i][k]);
			}
		}
		for(int j=1;j<=cnt && a[j]*i<=n;j++){
			p[a[j]*i]=1;
			if(i%a[j]==0){
				break;
			}
		}
	}
}
void dfs(int i,int cur,int v){
	if(i>cnt || cur*a[i]*a[i]>N){
		pnc[++pc]=cur;
		val[pc]=v;
		return;
	}
	for(int j=1,k=0;cur*j<=N;j=j*a[i],k++){
		if(j!=a[i]){
			dfs(i+1,cur*j,v*fp[a[i]][k]%md);
		}
	}
}
__int128_t getsum(int k){
	return (k*(k+1)/2)%md;
}
int t,n;
signed main(){
	inv[1]=1;
	for(int i=2;i<=50;i++){
		inv[i]=(md-md/i)*inv[md%i]%md;
	}
	sieve(1000000);
	read(t);
	dfs(1,1,1);
	while(t--){
		read(n);
		__int128_t res=0;
		for(int i=1;i<=pc;i++){
			res=(res+getsum(n/pnc[i])*val[i])%md;
		}
		printf("%lld\n",(long long)(res*powr(n,md-2)%md));
	}
	return 0;
}