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