#include<bits/stdc++.h>
using namespace std;

#define int long long

const int N=1e7+1e3+7,P=998244353;

int T,n;

int ans[N],vis[N],p[N],ptot,cnt[N],fr[N];

int f(int p,int k)
{
    if(p==2)
    {
        if(k==1)
            return 3;
        if(k==2)
            return 5;
        if(k==3)
            return 11;
        int ret=29,dlt=25;
        for(int t=4;t<k;t++)
        {
            ret=(ret*4-dlt+P)%P;
            if(t%2==1)
                dlt=(dlt+10)%P;
            else
                dlt=(dlt*4-53+P)%P;
        }
        // cerr<<dlt<<" ";
        return ret;
    }
    else
    {
        int ret=1;
        for(int t=1;t<=k;t++)
            ret=(ret*p%P-(t%2==0?p-1:(p-1)/2)+P)%P;
        return ret*ret%P;
    }
}

void pre(int n)
{
    ans[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(!vis[i])
            p[++ptot]=i,ans[i]=f(i,1),cnt[i]=1,fr[i]=1;
        for(int j=1;j<=ptot&&i*p[j]<=n;j++)
        {
            vis[i*p[j]]=1;
            ans[i*p[j]]=ans[i]*ans[p[j]]%P;
            if(i%p[j])
                cnt[i*p[j]]=1,fr[i*p[j]]=i;
            if(i%p[j]==0)
            {
                cnt[i*p[j]]=cnt[i]+1;
                fr[i*p[j]]=fr[i];
                ans[i*p[j]]=f(p[j],cnt[i*p[j]])*ans[fr[i*p[j]]]%P;
                break;
            }
        }
    }
    // for(int i=1;i<=50;i++)
    //     cout<<ans[i]<<"\n";
    for(int i=1;i<=n;i++)
        ans[i]=(ans[i]+ans[i-1])%P;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    pre(1e7);
    cin>>T;
    while(T--)
    {
        cin>>n;
        cout<<ans[n]<<"\n";
    }
}