#include<cstdio>
using namespace std;
const long long MOD = 666013;
long long N,H,T;
long long solve(long long x,long long h){
	if(x==0)
		return 1;
	if(x==1)
		return (2*(1LL<<(H-h)))%MOD;
	long long sol=solve(x/2,h+1);
	sol*=sol;
	if(x&1)
		sol<<=1;
	return sol%MOD;
}
void calc(){
	long long ax=1;
	H=0;
	while(ax+(1<<(H+1))<=N){
		++H;
		ax+=(1<<H);
	}
}
int main(){
	freopen("ciuperci.in","r",stdin);
	freopen("ciuperci.out","w",stdout);
	scanf("%lld",&T);
	for(;T;--T){
		scanf("%lld",&N);
		calc();
		printf("%lld\n",solve(N-(1<<(H+1))+1,0));
	}
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}