#include<fstream>
#define MOD 666013
using namespace std;
int Q;
long long n;

long long Nr()
{
	if(n==1)
		return 1;
	int i;
	long long aux=1,lim,sol=1;
	for(i=1;i<=64 && aux<n;i++)
	{
		aux=(1<<i);
		aux--;
		if(n==aux)
			return 1;
	}
	i-=2;
	lim=(1<<i);
	if(n%2==1)
		n--;
	for(i=lim;i<=n;i+=2)
	{
		sol=(sol*lim)%MOD;
		lim=lim-2;
	}
	return sol;
}

int main()
{
	int t;
	ifstream fin("ciuperci.in");
	ofstream fout("ciuperci.out");
	fin>>Q;
	for(t=0;t<Q;t++)
	{
		fin>>n;
		fout<<Nr()<<"\n";
	}
	fin.close();
	fout.close();
	return 0;
}