#include <cstdio>
using namespace std;

#define MOD 666013
#define MAXM 200000

FILE* fin = fopen("ciuperci.in", "r");
FILE* fout = fopen("ciuperci.out", "w");

typedef long long int64;
int mem[MAXM];

int64 num(int64 a)
{
	if (a <= 1) {
		return 1;	
	}
	
	if (a < MAXM && mem[a]) {
		return mem[a];	
	}
	
	int64 ret;
	if (a & 1) {
		int64 k = num(a >> 1);
		ret = (k * k) % MOD;	
	} else {
		int64 first = num(a >> 1);
		int64 second = num((a >> 1) - 1);
		
		ret = ((first * second) << 1) % MOD;
	}
	
	if (a < MAXM) {
		mem[a] = ret;	
	}
	return ret;
}

int main()
{
	int t;
	fscanf (fin, "%d\n", &t);
	
	for (int i = 0; i < t; ++i) {
		int64 a;
		fscanf (fin, "%lld", &a);		
		fprintf (fout, "%lld\n", num(a));	
	}
	
	fclose(fin);
	fclose(fout);
	return 0;
}