#include<iostream>
#include<cstdio>
using namespace std;
int ans=0;
int n;
int xx[4]={1,-1,0,0},yy[4]={0,0,-1,1};
void dfs(int yj,int yg,int x,int y){
	if(yj==yg){
		if(x==0&&y==0){
			ans=((ans%1997)+1)%1997;
		}
		return;
	}
	for(int j=0;j<=3;j++){
		int xxx=x+xx[j];
		int yyy=y+yy[j];
		if(xxx<=n/2&&xxx>=-n/2&&yyy<=n/2&&yyy>=-n/2){
			dfs(yj+1,yg,xxx,yyy);
		}
	}
}
int main(){
	freopen("diary.in","r",stdin);
	freopen("diary.out","w",stdout);
	int t;
	cin>>t;
	for(int i=1;i<=t;i++){
		cin>>n;
		ans=0;
		dfs(0,n,0,0);//已经走了0步，一共走n步，现在的坐标是（0，0） 
		cout<<(ans%1997)<<endl;
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}