#include <cstdio>
FILE *f,*g;
long long n;
int q,i;

long long sol(long long n) {
if (n==1) 
	return 1;
if (n==0)
	return 1;
if ( (n-1)%2==0) 
	return ( (long long)  ((sol( (long long)(n-1)/2 ) %666013)* ( sol ((long long) (n-1)/2) % 666013)) % 666013);
else 
	return ( (long long)2*((sol((long long)(n-1)/2)%666013)*(sol( (long long )(n-1)/2+1))%666013))%666013;

}

int main() {
f=fopen("ciuperci.in","r");
g=fopen("ciuperci.out","w");

fscanf(f,"%d",&q);

for (i=1;i<=q;i++) {
	fscanf(f,"%lld",&n);
	fprintf(g,"%lld\n",sol(n));
	}

fclose(g);
return 0;
}