// d[1]=1; d[2]=2;
// d[x]= (x%2==0) ? d[i / 2] * d[i / 2] : d[i / 2] * d[i / 2 - 1] * 2

#include <fstream>
using namespace std;

#define MOD 666013
#define DIM 8192
#define D2 33

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

long long H[DIM][D2];
int T;
long long N;

void Addd(long long N , long long x)
{
	long long r=N%DIM,t=N/DIM;
	H[r][t]=x;
}

long long Find(long long x)
{
	long long r=x%DIM,t=x/DIM;
	if (H[r][t])
		return H[r][t];
	return -1;
}

void Build(int N)
{
	if ( N%2 == 0 )
	{
		if (Find(N/2)==-1)
			Build(N/2);
		if (Find(N/2-1)==-1)
			Build(N/2-1);
		long long val=Find(N / 2);
		long long val2=Find(N / 2 - 1);
		val=( (val * val2) %MOD * 2 ) %MOD;
		Addd( N ,val );
	}
	else
	{
		if (Find(N/2)==-1)
			Build(N/2);
		long long value=Find(N / 2);
		value=(value * value) %MOD;
		Addd( N , value );
	}
}

void init()
{
	H[1][0]=1;
	H[0][0]=1;
	H[2][0]=2;
	fin>>T;
}

void solve()
{
	for (int i=1;i<=T;++i)
	{
		fin>>N;
		if (Find(N)==-1)
			Build(N);
		fout<<Find(N)<<'\n';
	}
}

int main()
{
	init();
	
	solve();
	
	return 0;
}