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

#define ll long long

#define dim 8192
#define mod 666013

using namespace std;

int pz;
char vec[dim + 5];

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;
	}
}
int solve(ll N) {
	if(N == 1 || N == 0) return 1;
	int ret1 = solve(N / 2);
	if(N & 1)
	       return (1LL * ret1 * ret1) % mod;
	int ret2 = solve(N / 2 - 1);
	return (1LL * ret1 * ret2 * 2) % mod;
}
	
int main() {


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