#include <iostream>
#include <fstream>
#include <algorithm>
#define MOD 666013
#define LL long long
#define x first
#define y second
using namespace std;


//N impar F(N) = F((N-1)/2)^2
//N par F(N) = 2 * (F(N/2-1) * F(N/2))

typedef pair<LL, LL> per;

per f(LL a, LL b) {
	if(a==0) return make_pair(1,1);
	if(a==1) return make_pair(1,2);
	per r=f(b/2-1,b/2),t;
	if(b&1) {
		t.y=(r.y*r.y)%MOD;
		t.x=(2LL*r.x*r.y)%MOD;
	}else {
		t.x=(r.x*r.x)%MOD;
		t.y=(2LL*r.x*r.y)%MOD;
	}
	return t;
}

LL fi(LL n) {
	if(n==1 || n==0) return 1;
	if(n==2) return 2;
	if(n&1) {
		LL r=fi(n/2);
		r=(r*r)%MOD;
		return r;
	}else {
		per r=f(n/2-1,n/2);
		return (2*r.first*r.second)%MOD;
	}
}

int main()
{
	ifstream f("ciuperci.in");
	ofstream g("ciuperci.out");
	int q;
	LL n;
	for(f>>q;q--;) {
		f>>n;
		g<<fi(n)<<'\n';
		cout<<fi(n)<<'\n';
	}
	return 0;
}