#include <fstream>
using namespace std;
const int MOD = 666013;
int ARBORE(long long N){
	if(N == 2)
		return 1;
	if(N == 1)
		return 0;
	if(N % 2 == 1){
		int x = ARBORE((N-1) / 2);
		return x + x;
	}
	else{
		int x = ARBORE(N / 2);
		int y = ARBORE((N - 1) / 2);
		return x + y + 1;
	}
}

int main() {
	ifstream fin("ciuperci.in");
	ofstream fout("ciuperci.out");
	int Q, N;
	fin >> Q;
	for(; Q; --Q){
		fin >> N;
		int power = ARBORE(N);
		long long rez = 1, a = 2;
		for(int i = 0; (1 << i) <= power; ++i){
			if(power & (1 << i))
				rez = ((long long)rez * a) % MOD;
			a = ((long long)a * a) % MOD;
		}

		fout << rez << '\n';

	}

	return 0;
}