#include<bits/stdc++.h> using namespace std; #include<atcoder/all> using namespace atcoder; using mint=atcoder::modint998244353; #define int long long template<long long mod,long long MAX_N> struct factional_prime{ long long inv_[MAX_N+1]; long long fac_[MAX_N+1]; long long fac_inv_[MAX_N+1]; factional_prime(){ inv_[0]=0;inv_[1]=fac_[0]=fac_[1]=fac_inv_[0]=fac_inv_[1]=1; for(long long i=2;i<=MAX_N;i++){ inv_[i]=((mod-mod/i)*inv_[mod%i])%mod; fac_[i]=(fac_[i-1]*i)%mod; fac_inv_[i]=(fac_inv_[i-1]*inv_[i])%mod; } } long long inv(long long n){ if(n<0)return 0; return inv_[n]; } long long fac(long long n){ if(n<0)return 0; return fac_[n]; } long long finv(long long n){ if(n<0)return 0; return fac_inv_[n]; } long long nCr(long long n,long long r){ if(n<r||n<0||r<0)return 0; return ((fac_[n]*fac_inv_[n-r])%mod*fac_inv_[r])%mod; } long long nPr(long long n,long long r){ if(n<r||n<0||r<0)return 0; return (fac_[n]*fac_inv_[n-r])%mod; } }; factional_prime<998244353,500000> fp; void slv(){ int n;cin>>n; if(n==1){ cout<<1<<endl; return ; } mint ans=mint(2).pow(n*(n-1)/2-1); mint ans2=mint(2).pow(n-2)-mint(3).pow(n-2)/mint(2).pow(n-2); ans2*=mint(2).pow(n*(n-1)/2-(n-1)); ans+=ans2; ans*=(n-1); ans+=mint(2).pow(n*(n-1)/2); cout<<ans.val()<<endl; } signed main(){ int t;cin>>t; while(t--){ slv(); } }