#include <fstream>
using namespace std;
const long long MOD = 666013;
long long ARBORE(long long N){
	if(N == 2)
		return 2;
	if(N == 1)
		return 1;
	if(N % 2 == 1){
		long long x = ARBORE((N-1) / 2);
		return (x * x) % MOD;
	}
	else{
		long long x = ARBORE(N / 2);
		long long y = ARBORE((N- 1) / 2);
		return (2 * x * y) % MOD;
	}
}
int main() {
	ifstream fin("ciuperci.in");
	ofstream fout("ciuperci.out");
	int Q;
	long long N;
	fin >> Q;
	for(; Q; --Q){
		fin >> N;
		fout << ARBORE(N) << '\n';
	}

	return 0;
}