#include <stdio.h>
#include <vector>
using namespace std;

typedef long long ll;
const char IN[]="ciuperci.in",OUT[]="ciuperci.out";
const int mod=64 , mmod = mod -1,prime = 5077 , pmod=666013 ;
int Q;
ll N;
vector<pair<ll,int> > v[mod];

int sqrm(int x){
	return 1LL*x*x%pmod;
}

int key(ll x){
	return ( 1LL*x*prime )&mmod;
}

void add(ll x,int val){
	int k=key(x);
	v[k].push_back(make_pair(x,val));
}

int q(ll x){
	int k=key(x);
	for (int i=0;i<v[k].size();++i) if ( v[k][i].first == x )
		return v[k][i].second;
	return -1;
}

int query(ll x)
{
	int r=q(x);
	if (r!=-1) return r;
	if (!(x&(x-1))) return x;
	if (x<=1) return 1;
	
	if ( x&1 )  r=sqrm(query(x/2));
	else r= 1LL*2*query(x/2)*query(x/2-1)%pmod;
	add(x,r);
	return r;
}

int main()
{
	freopen(IN,"r",stdin);
	freopen(OUT,"w",stdout);
	scanf("%d",&Q);
	while (Q--)
	{
		for (int i=0;i<mod;++i) v[i].clear();
		scanf("%lld\n",&N);
		printf("%d\n",query(N));
	}
	fclose(stdout);fclose(stdin);
	return 0;
}