#include<fstream>
#define MOD 666013
using namespace std;
ifstream in("ciuperci.in");
ofstream out("ciuperci.out");

int testNr;
long long nodesNr;


int trees(long long nodes)
{	
	if(nodes == 1)
		return 1;
	if(nodes == 2)
		return 2;
	if(nodes == 3)
		return 1;
	if(nodes == 4)
		return 4;
	else
	{	
		nodes--;
		long long mid = nodes / 2;
		
		if(nodes % 2 == 0)
		{	
			long long nr = trees(mid);
			long long res = nr*nr;
			
			if(res > MOD)
				res %= MOD;
			
			return res;
		}
		else
		{	long long nr1 = trees(mid);
			long long nr2 = trees(mid+1);
			long long res = 2*nr1*nr2;
			
			if(res > MOD)
				res %= MOD;
			
			return res;
		}
	}	
}	



int main()
{
	in>>testNr;
	
	for(; testNr; testNr--)
	{	
		in>>nodesNr;

		out<<trees(nodesNr)<<'\n';
	}
	in.close();

	out.close();
	return 0;
}