#include <fstream>
#include <vector>

using namespace std;

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

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

struct HashElement
{
	HashElement(long long N=0, int sol=0):N(N),sol(sol){};
	long long N;
	int sol;
};

int Q;
long long N;
vector<HashElement> H[HASH_MOD];

inline void HashInsert(const long long &val, const int &x)
{
	int key=val&(HASH_MOD-1);
	H[key].push_back(HashElement(val,x));
}

inline void HashInit()
{
	for(register int i=0;i<HASH_MOD;++i)
	{
		H[i].clear();
	}
	HashInsert(0,1);
	HashInsert(1,1);
}

inline int HashSearch(const long long &val)
{
	int key=val&(HASH_MOD-1);
	for(vector<HashElement>::iterator it=H[key].begin();it!=H[key].end();++it)
	{
		if(it->N==val)
		{
			return it->sol;
		}
	}
	return 0;
}

int Query(const long long &N)
{
	int val=HashSearch(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;
	}
	HashInsert(N,val);
	return val;
}

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