#include<bits/stdc++.h>
using namespace std;
const int mod=1997;
int t,n;
int qpow(int a,int b){
	int ans=1;
	while(b){
		if(b&1) ans=ans*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return ans%mod;
}
int fac[20005],inv[20005];
//int c(int x,int y){return fac[x]*inv[y]%mod*inv[x-y]%mod;}
int main(){
	freopen("diary.in","r",stdin);
	freopen("diary.out","w",stdout);
	fac[0]=fac[1]=1;
	for(int i = 2;i<=1996;i++) fac[i]=fac[i-1]*i%mod;
	inv[1996]=qpow(fac[1996],mod-2);
	for(int i = 1995;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
        int res=0;
		if(n%2==1){puts("0"); continue;}
		for(int i = 0;i<=n/2;i++)
		res=(res+(fac[n]*inv[i]%mod*inv[i]%mod*inv[n/2-i]%mod*inv[n/2-i]))%mod;
		printf("%d\n",res);
	}
	return 0;
}