//satyaki3794
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define LEFT(n) (2*(n))
#define RIGHT(n) (2*(n)+1)
 
using namespace std;
typedef long long ll;
typedef pair<ll, ll> ii;
typedef pair<int, ii> iii;
 
ll pwr(ll base, ll p, ll mod){
ll ans = 1;while(p){if(p&1)ans=(ans*base)%mod;base=(base*base)%mod;p/=2;}return ans;
}
 
 
ll gcd(ll a, ll b){
    if(b == 0)  return a;
    return gcd(b, a%b);
}
 
 
const int LG = 19;
const int maxn = (1<<LG);
const int G = 3;
const int MOD = 663224321;
 
int W[maxn>>1],invW[maxn>>1];
void precompute_powers(){
    W[0] = invW[0] = 1;
    int base = pwr(G, (MOD-1)/maxn, MOD);
    int inv_base = pwr(base, MOD-2, MOD);
    for(int i = 1;i<maxn/2;i++){
        W[i] = (W[i-1] * 1LL * base) % MOD;
        invW[i] = (invW[i-1] * 1LL * inv_base) % MOD;
    }
}
 
void ntt (vector<int> &a, bool invert) {
    int n = (int) a.size();
    for (int i=1, j=0; i<n; ++i) {
        int bit = n >> 1;
        for (; j>=bit; bit>>=1)
            j -= bit;
        j += bit;
        if (i < j)
            swap (a[i], a[j]);
    }
 
    for (int len=2; len<=n; len<<=1) {
        for (int i=0; i<n; i+=len) {
            int ind = 0, add = maxn/len;
            for (int j=0; j<len/2; ++j) {
                int u = a[i+j],  v = (a[i+j+len/2] * 1LL * (invert?invW[ind]:W[ind])) % MOD;
           // cout<<len<<" "<<i<<" "<<j<<" "<<u<<" "<<v<<" coz "<<ind<<" "<<W[ind]<<endl;
                a[i+j] = (u + v) % MOD;
                a[i+j+len/2] = (u - v + MOD) % MOD;
                ind += add;
            }
        }
    }
    if (invert){
        int inv_n = pwr(n, MOD-2, MOD);
        for (int i=0; i<n; ++i)
            a[i] = (a[i] * 1LL * inv_n) % MOD;
    }
}
 
 
const int N = 100003;
int limit = 100001;
int total_trees[N], ans[N];

ll count_rooted_trees(ll n){
    if(n == 0 || n == 1)    return 1;
    return (pwr(n, n-2, MOD) * n) % MOD;
}

 
void convolve(int l1, int r1, int l2, int r2){
  
    int sz = (r1-l1+1) + (r2-l2+1) - 1;
    int n = 1;
    while(n < sz)   n *= 2;
 
    vector<int> A(n, 0), B(n, 0);
    for(int i=l1;i<=r1;i++)
        A[i-l1] = ans[i];
    for(int i=l2;i<=r2;i++)
        B[i-l2] = total_trees[i];

 
    ntt(A, false);
    ntt(B, false);

    for(int i=0;i<n;i++)
        A[i] = (A[i] * 1LL * B[i]) % MOD;
    ntt(A, true);
 
    for(int i=0;i<n;i++){
        int idx = l1 + l2 + i + 1;
        if(idx <= limit)    ans[idx] = (ans[idx] + A[i]) % MOD;
    }
}
 
 
int main(){
 
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    precompute_powers();
    for(int i=0;i<=limit;i++){
        total_trees[i] = count_rooted_trees(i);
    }

    ans[0] = 1;
    for(int i=0;i<=limit;i++){

        if(i+1 <= limit)    ans[i+1] = (ans[i+1] + 1LL*ans[i]*total_trees[0]) % MOD;
        if(i+2 <= limit)    ans[i+2] = (ans[i+2] + 1LL*ans[i]*total_trees[1]) % MOD;

        for(int p=2;i>0 && i%p==0 && p<=limit;p*=2)
            convolve(i-p, i-1, p, min(2*p-1, limit));
    }

    int t;
    cin>>t;
    assert(t >= 1 && t <= 100000);
    while(t--){

        int n;
        cin>>n;
        assert(n >= 1 && n <= 100000);
        cout<<ans[n]<<endl;
    }

    return 0;
}