#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#define ll long long

#define dim 8192
#define mod 666013

#define hashkey 31
#define maxOP 22000
#define MAXCONST 1000000000ll
using namespace std;

int pz, nrop;
char vec[dim + 5];
set < pair <ll, int> > myset[hashkey+3];
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) {
	if(N > MAXCONST) return 0;
	int x = N & hashkey;
	set <pair <ll, int> > :: iterator itlow = myset[x].lower_bound(make_pair(N,0));
	
//	itlow++;
	
	if(itlow -> first == N)
		return itlow -> second;
	return 0;
}
inline void add(ll N, int val) {
	int x = N & hashkey;
	myset[x].insert(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(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);
	//	printf("%d\n", nrop);
		int r = solve(N);
	//	printf("%d\n", nrop);
		if(nrop > maxOP) {
			for(int i = 0; i <= hashkey; i++) {
				myset[i].clear();
			}
			nrop = 0;
		}
		printf("%d\n", r);	
	}
	return 0;
}