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

#define ll long long

#define dim 8192
#define mod 666013

#define hashkey 1747
#define maxOP 10000
#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;

	ret1 = find(N / 2);

	if(!ret1) {
		ret1 = solve(N / 2);
		if(nrop <= maxOP && N/2 <= MAXCONST)
			add(N/2, ret1), ++nrop;
	}
	if(N & 1) 
	       return (1LL * ret1 * ret1) % mod;
	ret2 = find(N / 2 - 1);

	if(!ret2) {
		ret2 = solve(N / 2 - 1);
		if(nrop <= maxOP && N/2 - 1 <= MAXCONST) add(N / 2 - 1, ret2), ++nrop;
	}
	return (1LL * ret1 * ret2 * 2) % mod;
}
	
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--; ) {
		cit(N);
		int r = solve(N);
		if(nrop > maxOP && !ok) {
			for(int i = 0; i < hashkey; i++)
				h[i].reserve(h[i].size() + 1);
			ok = 1;
		}
		printf("%d\n", r);
	}
	return 0;
}