#include <cstdio>
using namespace std;

#define MOD 666013

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

typedef long long int64;

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

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;
}