#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 == 0) {
		return 0;
	}
	
	if (a == 1 || a  == 3) {
		return 1;
	}
	
	if (a == 2) {
		return 2;
	}	
	
	return ((((a & 1) ? 2 : 1) * num(a >> 1)) % MOD * num(a - (a >> 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;
}