#include<fstream>
using namespace std;

#define pii pair<long long, long long>
#define X first
#define Y second
#define mod %666013
#define INF 18446744073709551615

ifstream f("ciuperci.in");
ofstream g("ciuperci.out");

long long Q, N;

long long arb(long long st, long long dr)
{	long long a, b, rez;
	
	if(st + dr + 1 == 1) return 1;
	if(st + dr + 1 == 2) return 2;
	if(st + dr + 1 == 3) return 1;
	if(st + dr + 1 == 4) return 4;
	
	if(st % 2) a = b = (st - 1) / 2;
	else a = (st - 1) / 2 , b = (st - 1) / 2 + 1;
	
	if(dr % 2) ((a == (dr - 1) / 2)? b : a) = (dr - 1) / 2;
	else a = (dr - 1) / 2 , b = (dr - 1) / 2 + 1;
	
	rez = arb(a, b) mod;
	return ((rez mod) * ( rez mod) ) mod;
}
	

int main()
{	
	f>>Q;
	while(Q--)
	{	f>>N;
		if(N == 1 || N == 2) g<<N<<'\n';
		else
		if(N % 2)
			g<<arb((N - 1) / 2, (N - 1) / 2) mod<<'\n';
		else g<<arb((N - 1) / 2, (N - 1) / 2 + 1) mod<<'\n';
	}
	f.close();
	g.close();
	return 0;
}