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

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

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;
}