using namespace std;
#include<fstream>
#define ll long long
const int mod = 666013;
int Q;
ll memo( ll n )
{
	if(n == 1 || n == 0) return 1;
	ll tmp;
	ll v;
	if( n & 1 )
	{
		tmp = memo(n/2);
		v = ( 1LL * tmp * tmp ) % mod;
		return v;
	}
	tmp = memo(n/2);
	tmp = ( 1LL * tmp * 2 ) % mod;
	tmp = ( 1LL * tmp * 1LL * memo(n/2 - 1) ) % mod;
	return tmp % mod;
}
int main()
{
	ifstream in("ciuperci.in"); ofstream out("ciuperci.out");
	in >> Q;
	ll N;
	for(;Q;--Q)
	{
		in >> N;
		out << memo(N)<< "\n";
	}
	return 0;
}