#include <stdio.h>

#define MOD 666013

using namespace std;


long long n,sol,i,j,k,d,r,x,t,q,y,nr1,nr2,nr3,z;
long long p[64];

int main () {
	freopen("ciuperci.in","r",stdin);
	freopen("ciuperci.out","w",stdout);
	scanf("%d",&q);
	p[0]=1; p[1]=2;
	for (i=2; i<=60; ++i) p[i]=p[i-1]*2;
	for (t=1; t<=q; ++t) {
		scanf("%lld",&n);
		for (i=0; i<=60; ++i) 
			if (p[i]>n) {
				x=i-1;
                break;
			}
		k=n-p[x]+1;
        x--;
		sol=1;
		if (p[x+1]==k) printf("1\n");
		else {
		if (k%2==1) sol=2;
		for (i=1,y=p[x]; i<=x; ++i, y/=2) {
			d=k/p[i];
			r=k%p[i];
			
			if ((d==1) /*|| (d==2 && r==0)*/) {
				nr2=r;
				nr1=k-2*nr2;
				for (j=1; j<=nr1; ++j) 
					sol=(sol*y)%MOD;
				z=(y/2)*(y/2);
				for (j=1; j<=nr2; ++j)
					sol=(sol*z)%MOD;
			}
			else 
			if (d!=0){
				if (d%2==0) nr3=r;
				else nr3=p[i]-r;
				for (j=1; j<=nr3; ++j)
					sol=(sol*2)%MOD;
			}
		}
		printf("%lld\n",sol);
		}
	}
	return 0;
}