#include<bits/stdc++.h>
#define int long long
#define mod 998244353
using namespace std;
#define abs(x) (x>=0?x:-x)
int qpow(int i,int j){return j?j&1?qpow(i*i%mod,j>>1)*i%mod:qpow(i*i%mod,j>>1):1;}
signed main()
{
    int t;
    scanf("%lld",&t);
    while(t--)
    {
        int n;
        scanf("%lld",&n);
        vector<long long>cnt(31),s(31);
        for(int i=0;i<=30;i++)
        {
            cnt[i]=((n>>i+1)<<i);
            cnt[i]+=max(0ll,n%(2<<i)-(1<<i));
        }
        for(int i=0;i<=30;i++)
        {
            s[i]=cnt[i]*(1<<i);
            if(i)s[i]+=s[i-1];
        }
        long long ans=0;
        function<void(int,int,int)>dfs=[&](int l,int k,long long sum)
        {
            if(k==-1||abs(sum)>s[k])
            {
                // cerr<<l<<k<<sum<<endl;
                ans+=max(0ll,sum%mod*(1<<k+1)%mod);
                // if(sum>0)ans+=n*(l+l+(1<<k+1)-1)%mod*(1<<k+1)%mod+sum%mod;
                // else ans+=n*(l+l+(1<<k+1)-1)%mod*(1<<k+1)%mod;
                return;
            }
            dfs(l,k-1,sum+cnt[k]*(1<<k));
            dfs(l+(1<<k),k-1,sum-cnt[k]*(1<<k));
        };
        long long sum0=0,lst=0;
        for(int l=30;l>=0;l--)
        {
            if(lst+(1<<l)<=n)
            {
                dfs(lst,l-1,sum0+cnt[l]*(1<<l));
                lst+=(1<<l);
                sum0-=cnt[l]*(1<<l);
            }
        }
        // printf("%d\n",ans);
        ans+=(n-1)*n/2%mod*n%mod;
        printf("%lld\n",ans%mod*qpow(n*n%mod,mod-2)%mod);
    }
    return 0;
}