#pragma GCC optimize("O3")
#define _CRT_SECURE_NO_WARNINGS
#include <fstream>
#include <iostream>
#include <string>
#include <complex>
#include <math.h>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <stdio.h>
#include <stack>
#include <algorithm>
#include <list>
#include <ctime>

#include <memory.h>
#include <assert.h>

#define y0 sdkfaslhagaklsldk

#define y1 aasdfasdfasdf
#define yn askfhwqriuperikldjk
#define j1 assdgsdgasghsf
#define tm sdfjahlfasfh
#define lr asgasgash
#define norm asdfasdgasdgsd
#define have adsgagshdshfhds
#define ends asdgahhfdsfshdshfd
#define right asdashgasrhsdf

#define eps 1e-14
#define M_PI 3.141592653589793
#define bs 663224321
#define bsize 64

#define ldouble long double

using namespace std;

long long INF = 1e9;
const int N = 100031;

long long fact[N];
long long invf[N];

long long dp[N];

long long pw(long long a,long long b)
{
	if (b==0)
		return 1;
	if (b%2)
		return a*pw(a,b-1)%bs;
	return pw(a*a%bs,b/2);
}

long long inv(long long x)
{
	return pw(x,bs-2);
}

long long C(long long n,long long m)
{
	if (m>n)
		return 0;
	long long res=fact[n];
	res*=invf[m];
	res%=bs;
	res*=invf[n-m];
	return res%bs;
}

int tests;
long long memopw[N];

int main(){
	//freopen("tree.in","r",stdin);
	//freopen("tree.out","w",stdout);
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
	ios_base::sync_with_stdio(0);
	//cin.tie(0);

	fact[0]=1;
	for (int i=1;i<N;i++)
	{
		fact[i]=fact[i-1]*i%bs;
	}

	for (int i=1;i<=10000;i++)
	{
		memopw[i]=pw(2,i*(i-1)/2);
	}
	for (int i=0;i<N;i++)
	{
		invf[i]=inv(fact[i]);
	}


	for (int i=1;i<=10000;i++)
	{
		long long here=pw(2,1ll*i*(i-1)/2);
		long long sub=0;
		for (int j=1;j<i;j++)
		{
			sub+=j*C(i,j)%bs*memopw[i-j]%bs*dp[j]%bs;
			sub%=bs;
		}
		sub*=inv(i);
		sub%=bs;
		dp[i]=here-sub+bs;
		dp[i]%=bs;
	}

/*	for (int i=1;i<=10;i++)
	{
		cout<<dp[i]<<" ";
	}
	cout<<endl;
*/
	int mx=0;

	cin>>tests;
	for (;tests;--tests)
	{
		int n;
		cin>>n;
		mx=max(mx,n);
		cout<<dp[n]<<endl;
	}

	assert(mx<=10000);

	cin.get(); cin.get();
	return 0;
}