#include <fstream>
using namespace std;

#define MOD 666013

long long i,T,N,Ni,Nd,Nl,S,R;

ifstream fin("ciuperci.in");
ofstream fout("ciuperci.out");

long long put(long long a, long long p) {
	long long rez=1;
	while(p) {
		if(p&1) rez=(rez*a)%MOD;
		a=(a*a)%MOD;
		p/=2;
	}
	return rez;
}

long long comb(long long N, long long K){
	long long rez=1;
	for(long long t=N-K+1;t<=N;t++)
		rez=(rez*t)%MOD;
	for(long long t=2;t<=K;t++)
		rez=((rez+MOD)/t)%MOD;
	return rez;
}

int main() {
	for(fin>>T;T;T--) {
		fin >> Ni;
		
		N=1; S=1;
		for(i=1; S+(1LL<<i)<=Ni ;i++)
			S+=(1LL<<i);
		N=1LL<<(i-1);
		Nd=Ni-S;
		
		if(Nd<=N) {
			Nl=N-Nd;
			R=(put(2,Nd)*comb(N,Nl))%MOD;
		}
		else {
			Nd=Nd-N;
			Nl=N-Nd;
			R=(put(2,Nl)*comb(N,Nl))%MOD;
		}
		fout << R << '\n';
	}
}