#include <fstream>
#include <map>

using namespace std;

const char InFile[]="ciuperci.in";
const char OutFile[]="ciuperci.out";
const int MOD=666013;

ifstream fin(InFile);
ofstream fout(OutFile);

int Q;
long long N;
map<long long,int> sol;

int Query(long long N)
{
	int val=sol[N];
	if(val)
	{
		return val;
	}
	int half=Query(N>>1);
	if(N&1)
	{
		val=(1LL*half*half)%MOD;
	}
	else
	{
		val=(1LL*half*Query((N>>1)-1)<<1)%MOD;
	}
	sol[N]=val;
	return val;
}

int main()
{
	sol[0]=sol[1]=1;
	fin>>Q;
	for(register int i=1;i<=Q;++i)
	{
		sol.clear();
		sol[0]=sol[1]=1;
		fin>>N;
		fout<<Query(N)<<"\n";
	}
	fin.close();
	fout.close();
	return 0;
}