#include<stdio.h>
#define mod 666013
FILE*f=fopen("ciuperci.in","r");
FILE*g=fopen("ciuperci.out","w");

int D[100000],i,x,t;

int main () {
	
	D[1] = 1; D[2] = 2; //Z[2] = 1;
	for ( i = 3 ; i <= 99999 ; ++i ){
		if ( i & 1 ){
			D[i] = (1LL*D[i/2] * D[i/2])%mod;
			//Z[i] = Z[i/2] + Z[i/2];
		}
		else{
			D[i] = (1LL*2 * D[(i-1)/2] * D[((i-1)/2)+1])%mod;
			//Z[i] = 1 + Z[i/2] + Z[(i/2)+1];
		}
	}
	fscanf(f,"%d",&t);
	for ( i = 1 ; i <= t; ++i ){
		if ( x >= 99999 )	while(1){};
		fscanf(f,"%d",&x);
		fprintf(g,"%d\n",D[x]);
	}
	
	fclose(f);
	fclose(g);
	
	return 0;
}