#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <cassert>
using namespace std;

const  int N = 10005;
const int MOD = 663224321;
const int LIM = 10000000;

int C[N][N];
int dc[N], cn[N], p2[LIM];

inline int exp_m(int y) {
    if (y < LIM) {
        return p2[y];
    }
    if (y == 0) {
        return 1;
    }
    int q = exp_m(y >> 1);
    q = (long long)q * q % MOD;
    if (y & 1) {
        q = (q << 1) % MOD;
    }
    return q;
}
int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
    C[0][0] = 1;
    for (int i = 1; i < N; i++) {
        C[i][0] = 1;
        for (int j = 1; j < N; j++) {
            C[i][j] = (C[i -1 ][j - 1] + C[i - 1][j]) % MOD;
        }
    }

    p2[0] = 1;
    for  (int i = 1; i < LIM; i++) {
        p2[i] = (p2[i - 1] * 2) % MOD;
    }
    
    cn[1] = 1;
    dc[1] = 0;
    for (int i = 2; i < N; i++) {
        cn[i] = exp_m(i * (i - 1) / 2);
        dc[i] = 0;
        for (int j = 1; j < i; j++) {
            long long cur = C[i - 1][j - 1];
            cur = (cur * cn[j]) %MOD;
            cur = (cur * exp_m((i - j) * (i - j - 1) / 2)) % MOD;
            dc[i] = (dc[i] + cur) % MOD;
        }
        cn[i] = (cn[i] - dc[i] + MOD) % MOD;
    }
    /*
    for (int i = 0; i < 50; i++) {
        cout << cn[i] << " " ;
    }
    cout << endl;
    */
    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        int n;
        cin >> n;
        assert(n < N);
        cout << cn[n] << endl;
    }
    return 0;
}