#include<cstdio>
using namespace std;
const long long MOD = 666013LL;
long long N,T,mem[1010];
long long solve(long long X){
	if(X<=1000 && N)
		return mem[X];
	if((X^(X+1))==X)
		return 1;
	if(X==1)
		return 1;
	if(X==2)
		return 2;
	if(X&1){
		long long sol=solve(X>>1);
		return (sol*sol)%MOD;
	}
	return (solve((X-1)>>1)*solve(X>>1)*2)%MOD;
}
int main(){
	freopen("ciuperci.in","r",stdin);
	freopen("ciuperci.out","w",stdout);
	for(int i=1;i<=1000;++i)
		mem[i]=solve(i);
	scanf("%lld",&T);
	for(;T;--T){
		scanf("%lld",&N);
		printf("%lld\n",solve(N));
	}
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}