#include<stdio.h>

#define MOD 666013

int t,val,a,b;
int el[105][2];
int v[105][2];
long long sola,solb;
int d[13];

int main ()
{
	int i,j,pinc,psf;

	freopen("ciuperci.in","r",stdin);
	freopen("ciuperci.out","w",stdout);
	d[1]=d[3]=1;
	d[2]=2;d[4]=4;
	scanf("%d",&t);
	for(;t;t--)
	{
		scanf("%d",&val);
		el[0][1]=el[0][0]=val;
		
		for(pinc=0,psf=0;pinc<=psf;pinc++)
		{
			if(el[pinc][0]<=2 || el[pinc][1]<=2)
				break;
			a=el[pinc][0]-1;
			b=el[pinc][1]-1;
			el[++psf][0]=a/2;
			el[psf][1]=0;
			if(a-a/2>el[psf][0] || a-a/2<el[psf][0])
				el[psf][1]=a-a/2;
			if(b/2>el[psf][0] || b/2<el[psf][0])
				el[psf][1]=b/2;
			if(b-b/2>el[psf][0] || b-b/2<el[psf][0])
				el[psf][1]=b-b/2;
			if(!el[psf][1])
				el[psf][1]=el[psf][0];
		}
		v[pinc][0]=d[el[pinc][0]];
		v[pinc][1]=d[el[pinc][1]];
		for(i=pinc-1;i>=0;i--)
			for(j=0;j<=1;j++)
			{
				a=(el[i][j]-1)/2;
				b=el[i][j]-1-a;
				if(a==el[i+1][0])
					sola=v[i+1][0];
				else
					sola=v[i+1][1];
				if(b==el[i+1][0])
					solb=v[i+1][0];
				else
					solb=v[i+1][1];
				if(a==b)
					v[i][j]=(sola*solb)%MOD;
				else
					v[i][j]=(2*sola*solb)%MOD;
			}	
		printf("%d\n",v[0][0]);
	}
	return 0;
}