# your code goes here#include<bits/stdc++.h>

typedef long long LL;
typedef __int128 IT;
//typedef long long IT;

const int ny6=166374059;
const int MOD=998244353;
const int N=10000005;
const int maxn=10000000;

int phi[N],tot,prime[N/10];
bool not_prime[N];
IT n;

template <class T>
void read(T &x)
{
    static char ch;
    static bool neg;
    for(ch=neg=0; ch<'0' || '9'<ch; neg|=ch=='-',ch=getchar());
    for(x=0; '0'<=ch && ch<='9'; (x*=10)+=ch-'0',ch=getchar());
    x=neg?-x:x;
}

int add(int x,int y) {return x+y<MOD?x+y:x+y-MOD;}

IT read()
{
	IT x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

void get_prime(int n)
{
	phi[1]=1;
	for (int i=2;i<=n;i++)
	{
		if (!not_prime[i]) prime[++tot]=i,phi[i]=i-1;
		for (int j=1;j<=tot&&i*prime[j]<=n;j++)
		{
			not_prime[i*prime[j]]=1;
			if (i%prime[j]==0)
			{
				phi[i*prime[j]]=phi[i]*prime[j];
				break;
			}
			phi[i*prime[j]]=phi[i]*(prime[j]-1);
		}
	}
}

int sqrt3(IT n)
{
	int l=1,r=maxn;
	while (l<=r)
	{
		int mid=(l+r)/2;
		if ((IT)mid*mid*mid<=n) l=mid+1;
		else r=mid-1;
	}
	return l-1;
}

int solve1(int n,LL m)
{
	int ans=n;
	for (int i=1;i*i<=n;i++)
		if (n%i==0)
		{
			ans=add(ans,(LL)(m/i)%MOD*phi[i]%MOD);
			if (n/i!=i) ans=add(ans,(LL)(m/(n/i))%MOD*phi[n/i]%MOD);
		}
	return ans;
}

int get1(int n)
{
	return (LL)n*(n+1)/2%MOD;
}

int get2(int n)
{
	return (LL)n*(n+1)%MOD*(n*2+1)%MOD*ny6%MOD;
}

int solve2(int n)
{
	int ans=0;
	for (int i=1;i<=n;i++) ans=add(ans,(LL)phi[i]*((LL)3*i*get2(n/i)%MOD+(LL)3*get1(n/i)%MOD+(LL)n/i)%MOD);
	return ans;
}

int main()
{
	get_prime(maxn);
	int T;scanf("%d",&T);
	while (T--)
	{
		read(n);
		int r=sqrt3(n),ans=add(solve1(r,(LL)(n-(IT)r*r*r)),solve2(r-1));
		printf("%d\n",ans);
	}
	return 0;
}