#include <stdio.h>
#include <algorithm>
#include <vector>
#define ll long long
#define MOD 666013
#define LMAX 21
#define f first
#define s second
#define pb push_back
#define mp make_pair
using namespace std;
int t,r,act;
ll n,act2;
vector < pair<ll,int> > A[33];
char line[LMAX];
inline int cif(char x)
{
	return x>='0' && x<='9';
}
inline int find(ll n,int where)
{
	int i;
	for (i=0; i<A[where].size(); i++)
		if (A[where][i].f==n)
			return A[where][i].s;
	return -1;
}
inline int calcul(ll n)
{
	if (n==0)
		return 1;
	if (n==1)
		return 1;
	int nr=n & 31,act=find(n,nr);
	if (act!=-1)
		return act;
	if (n & 1)
	{
		act2=calcul(n/2);
		act2=act2*act2;
		if (act2>=MOD)
			act2=act2-act2/MOD*MOD;
		act=act2;
	}
	else
	{
		act2=(ll)calcul(n/2)*calcul(n/2-1)*2;
		if (act2>=MOD)
			act2=act2-act2/MOD*MOD;
		act=act2;
	}
	A[nr].pb(mp(n,act));
	return act;
}
void sterge()
{
	int i;
	for (i=0; i<=31; i++)
		A[i].clear();
}
int main()
{
	freopen("ciuperci.in","r",stdin);
	freopen("ciuperci.out","w",stdout);
	scanf("%d\n",&t);
	int poz;
	while (t--)
	{
		n=0; poz=0;
		fgets(line+1,LMAX,stdin);
		while (cif(line[poz+1])) { poz++; n=n*10+line[poz]-'0';}
		r=0;
		printf("%d\n",calcul(n));
		sterge();
	}
	return 0;
}