#include<bits/stdc++.h>

using namespace std;

const int MAXN = 5e3 + 10;
const int MOD = 663224321;

int c1[MAXN][MAXN], c2[MAXN][MAXN], d[MAXN];

int pw(int a, int b){
	int ret = 1;
	while (b){
		if (b & 1)
			ret = 1ll*ret*a%MOD;
		b >>= 1;
		a = 1ll*a * a % MOD;
	}
	return ret;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	c1[0][0] = c2[0][0] = 1;
	for (int i = 1; i < MAXN; i++){
		c1[i][0] = c1[i][i] = c2[i][0] = c2[i][i] = 1;
		for (int j = 1; j < i; j++){
			c1[i][j] = c1[i - 1][j] + c1[i - 1][j - 1];
			while (c1[i][j] >= MOD) c1[i][j] -= MOD;

			c2[i][j] = c2[i - 1][j] + c2[i - 1][j - 1];
			while (c2[i][j] >= MOD - 1) c2[i][j] -= MOD-1;
		}
	}
	
	d[0] = d[1] = d[2] = 1;
	for (int i = 3; i < MAXN; i++){
		d[i] = 1ll*i*pw(2, c2[i][2]) % MOD;
		int temp = pw(i, MOD - 2);
		d[i] = 1ll*d[i]*temp % MOD;
		for (int k = 0; k < i; k++)
			d[i] = (d[i] - 1ll*c1[i][k]*k%MOD*d[k]%MOD*pw(2, c2[i - k][2])%MOD*temp%MOD+MOD) % MOD;
	}
	int q; cin >> q;
	while (q--){
		int n;	cin >> n;
		cout << d[n] << "\n";
	}
	return 0;
}