#include<bits/stdc++.h>
using namespace std;
int T,N;
int sum;
int zz[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
void dfs(int n,int x,int y){
	if(!n){
		if(!x&&!y) sum=(sum+1)%1997;
		return ;
	}
	for(int i=0;i<4;i++){
		int xx=x+zz[i][0],yy=y+zz[i][1];
		if(1000>=xx&&xx>=-1000&&1000>=yy&&yy>=-1000){
			dfs(n-1,xx,yy);
		}
	}	
	return ;
}
int main(){
	freopen("diary.in","r",stdin);
	freopen("diary.out","w",stdout);
	cin>>T;
	while(T--){
		cin>>N;
		sum=0;
		dfs(N,0,0);
		cout<<sum<<endl;
	}
	return 0;
}