using namespace std;
#include<fstream>
#include<vector>
#define ll long long
const int mod = 666013;
int Q;
vector<pair<ll,ll> > H[mod];
void insert( ll n, ll v )
{
	ll k = n % mod;
	pair<ll, ll> p = make_pair(n, v); 
	H[k].push_back(p);
}
ll find( ll n )
{
	ll k = n % mod;
	for(int i = 0; i < (int)H[k].size(); ++i)
		if( H[k][i].first == n ) return H[k][i].second;
	return -1;
}
ll memo( ll n )
{
	if(n == 1 || n == 0) return 1;
	ll tmp;
	tmp = find(n);
	if( tmp != -1 ) return tmp;
	ll v;
	if( n & 1 )
	{
		tmp = memo(n/2);
		v = ( 1LL * tmp * tmp ) % mod;
		insert( n, v );
		return v;
	}
	tmp = memo(n/2);
	tmp = ( 1LL * tmp * 2 ) % mod;
	tmp = ( 1LL * tmp * 1LL * memo(n/2 - 1) ) % mod;
	insert( n, tmp );
	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;
}