#include <fstream>
using namespace std;
const long long MOD = 666013;
int MODULO[100005];
int ARBORE(long long N){
	if(N == 2)
		return 2;
	if(N == 1)
		return 1;
	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;
	MODULO[0] = 1;
	for(int i = 1; i <= 1000; ++i)
		MODULO[i] = (MODULO[i - 1] * 2) % MOD;
	long long N;
	fin >> Q;
	for(; Q; --Q){
		fin >> N;
		fout << MODULO[ARBORE(N)] << '\n';
	}

	return 0;
}