#include <bits/stdc++.h>

using namespace std;

int mod = 663224321;

int PowMod(int n)
{
    int ret = 1;
    int a = 2;
    while (n > 0) {
        if (n & 1) ret = ret * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return ret;
}

long long degree(long long a, long long k, long long p) {
  long long res = 1;
  long long cur = a;

  while (k) {
    if (k % 2) {
      res = (res * cur) % p;
    }
    k /= 2;
    cur = (cur * cur) % p;
  }
  return res;
}

int get_degree(long long n, long long p) { // returns the degree with which p is in n!
  int degree_num = 0;
  long long u = p;
  long long temp = n;

  while (u <= temp) {
    degree_num += temp / u;
    u *= p;
  }
  return degree_num;
}

int combinations(int n, int k, long long p) {
  int num_degree = get_degree(n, p) - get_degree(n - k, p);
  int den_degree = get_degree(k, p);

  if (num_degree > den_degree) {
    return 0;
  }
  long long res = 1;
  for (long long i = n; i > n - k; --i) {
    long long ti = i;
    while(ti % p == 0) {
      ti /= p;
    }
    res = (res * ti) % p;
  }
  for (long long i = 1; i <= k; ++i) {
    long long ti = i;
    while(ti % p == 0) {
      ti /= p;
    }
    res = (res * degree(ti, p-2, p)) % p;
  }
  return int(res);
}

int sol(int n){
  vector<int> ck(n+1,0);
  ck[1] = 1;
  for(int i=2; i<=n; i++){
    ck[i] = PowMod(combinations(i,2,mod));
    int tmpSum = 0;
    for(int j = 1; j<i; j++){
      tmpSum += j*combinations(i,j,mod)*PowMod(combinations(i-j,2,mod))*ck[j];
    }
    ck[i] -= tmpSum/i;
    if(ck[i] < 0){
      ck[i] += mod;
    }
  }
  return ck[n];
}

int main(){
    int q;
    cin >> q;
    for(int a0 = 0; a0 < q; a0++){
        int n;
        cin >> n;
        cout << sol(n) << endl;
    }
    return 0;
}