#include <cstdio>
#include <cstring>
#include <string>
#include <vector>

#define ll long long

#define dim 8192
#define mod 666013

#define hashkey 2851
#define maxOP 32500
#define MAXCONST 10000000000ll
using namespace std;

int pz, nrop;
char vec[dim + 5];
vector <pair <ll, int> > h[hashkey+1];
inline void cit(ll &x) {
	x = 0;
	while(vec[pz] < '0' || vec[pz] > '9')
		if(++pz == dim) fread(vec, 1, dim, stdin), pz = 0;
	while(vec[pz] >= '0' && vec[pz] <= '9') {
		x = x * 10 + vec[pz] - '0';
		if(++pz == dim) fread(vec, 1,
			       	dim, stdin), pz = 0;
	}
}

inline int find(ll N) {
	int x = N % hashkey;
	for(vector <pair <ll, int> > :: iterator it = h[x].begin(); it != h[x].end(); it++)
		if(it -> first == N)
			return it -> second;
	return 0;
}
inline void add(ll N, int val) {
	int x = N % hashkey;
	h[x].push_back(make_pair(N, val));
}
int solve(ll N) {
	if(N == 1 || N == 0) return 1;
	
	int ret1, ret2;
	
	int x = find(N);
	
	if(x) return x;
	
	ret1 = solve(N/2);
	int sol = 0;
	if(N & 1) 
	       sol = (1LL * ret1 * ret1) % mod;
	else {
		ret2 = solve(N / 2 - 1);
		sol= (1LL * ret1 * ret2 * 2) % mod;
	}
	if(nrop <= maxOP && N <= MAXCONST) add(N, sol), ++nrop;
	return sol;
}
	
int main() {


	freopen("ciuperci.in", "r", stdin);
	freopen("ciuperci.out", "w", stdout);
	
	ll N;
	int Q; //bool ok = 0;
	
	for(scanf("%d\n", &Q); Q--; ) {
		//scanf("%lld\n", &N);
		cit(N);
		int r = solve(N);

		if(nrop > maxOP) {
			for(int i = 0; i < hashkey; i++) {
				h[i].erase(h[i].begin(), h[i].end());
				nrop = 0;
			}
		}

		printf("%d\n", r);
	}
	return 0;
}