#include <bits/stdc++.h>
using namespace std;

typedef long long Long;
typedef unsigned long long Ulong;

const Long MOD = 663224321;
const int NN = 100005;

Long modexp(Long base,Long po) {
  Long result = 1;
  while (po > 0) {
    if (po & 1)
      result = (result * base) % MOD;
    base = (base * base) % MOD;
    po = po >> 1;
  }
  return result;
}

Long FA[NN], IFA[NN], D[NN];

Long bino(Long N,Long K) {
  if (N < K) return 0;
  Long ans = (FA[N] * IFA[K]) % MOD;
  return (ans * IFA[N-K]) % MOD;
}

void precompute() {
  FA[0] = IFA[0] = FA[1] = IFA[1] = 1;
  for (int i = 2; i < NN; ++i) {
    FA[i] = (FA[i-1] * i) % MOD;
    IFA[i] = modexp(FA[i],MOD-2);
  }
  D[1] = D[2] = 1;
  for (Long i = 2; i < 5000; ++i) {
    D[i] = (i * modexp(2, i*(i-1)/2));
    for (Long j = 1; j < i; ++j) {
      Long cur_term = (bino(i,j)*j) % MOD;
      cur_term = (cur_term * D[j]) % MOD;
      cur_term = (cur_term * modexp(2,(i-j)*(i-j-1)/2)) % MOD;
      D[i] = (D[i] + MOD*2 - cur_term) % MOD;
    }
    D[i] = (D[i] * modexp(i, MOD-2)) % MOD;
  }
}

int main() {
  precompute();
  int T, N; scanf("%d", &T);
  while (T--) {
    scanf("%d", &N);
    printf("%lld\n",D[N]);
  }
  return 0;
}