#include <fstream>

using namespace std;

ifstream in("ciuperci.in");
ofstream out("ciuperci.out");

int x,q;


int ciuperci(int a){
	int aux;
	if(a==1) 
		return 1;
	if(a==2)
		return 2;
	aux=a-1;
	int st,dr;
	st=aux/2;
	dr=aux-st;
	int aux2=1;
	if(st!=dr)
		aux2=2;
	return (aux2*ciuperci(st)%666013)*(ciuperci(dr)%666013)%666013;
}

int main(){
	in>>q;
	for(int i=1;i<=q;++i){
		in>>x;
		out<<ciuperci(x)%666013<<"\n";
	} 
	return 0;
}