#include <stdio.h>
#define MOD 666013
#define LL long long

LL t,n,x,y,i,a,b;

void ciuperci(LL x,LL y,LL &a,LL &b)
{
	if (x<2 && y<2) 
	{ 
		a=b=1;
		return;
	}
	
	LL a2,b2;
	
	ciuperci((x-1)/2,y-1-(y-1)/2,a2,b2);
	
	if ((x-1)/2 == x-1-(x-1)/2) a=(a2*a2)%MOD;
		else a=(2*a2*b2)%MOD;
	if ((y-1)/2 == y-1-(y-1)/2) b=(b2*b2)%MOD;
		else b=(2*a2*b2)%MOD;
}

int main()
{
    freopen("ciuperci.in","r",stdin);
    freopen("ciuperci.out","w",stdout);
    
    scanf("%d",&t);
    for (i=1;i<=t;i++)
    {
		scanf("%lld",&n);
		ciuperci((n-1)/2,(n-1)-(n-1)/2,a,b);
		if (n%2) printf("%lld\n",(a*b)%MOD);
			else printf("%lld\n",(2*a*b)%MOD);
    }
}