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;
	if( n == 2) return 2;
	ll tmp;
	ll v;
	if( n & 1 )
	{
		tmp = memo(n>>1);
		v = ( 1LL * tmp * tmp ) % mod;
		return v;
	}
	v = 2;
	if( (n>>1) & 1 )
	{
		tmp = memo(n>>2);
		v = (v* tmp * tmp ) % mod;
		v = ( 1LL * 2 * v * tmp) % mod;
		v = ( 1LL * v * memo( (n/2-1)/2-1 ) ) % mod;
	}
	else
	{
		tmp = memo((n>>2) - 1);
		v = ( v * tmp * tmp ) % mod;
		v = ( v * 2 * tmp ) % mod;
		v = ( v * memo(  n >> 2 ) ) % mod;
	}
	return v % 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;
}