# include <fstream>
# include <iostream>
# define ll long long
# define P 666013
using namespace std;
ll p[100], n, q;

void pu ()
{
	p[0]=1;
	for(int i=1;i<63;++i)
		p[i]=p[i-1]*2;
}

void f ()
{
	q=1;
	while (p[q+1]-1<=n)++q;
	n-=p[q]-1;
	q=p[q-1];
}

ll calc (int unu, int doi)
{
	if (unu==1)
		return (2*(unu+doi))%P;
	if (doi==1)
		return (p[unu]%P*(unu+doi))%P;
	int u1=unu/2, u2=unu-u1, d1=doi/2, d2=doi-d1;
	if (u1!=u2 || d1!=d2)
		return (2*calc(u1, d1)*calc(u2,d2))%P;
	ll r=calc(u1, d1);
	return (r*r)%P;
}

int solve ()
{
	f();
	int unu, doi;
	if (n<=q)unu=q, doi=0;
	else doi=n-q, unu=n-doi;
	return calc(unu, doi);
}

int main ()
{
	pu();
	ifstream fin ("ciuperci.in");
	freopen("ciuperci.out", "w", stdout);
	int t;
	fin>>t;
	for(;t--;)
	{
		fin>>n;
		printf("%d\n", solve());
	}
	return 0;
}