#include <cstdio>
#include <vector>
#include<string>
using namespace std;

struct ciuperca{
    long long x, y;
};

const int mod = 666013, auxmod = 31;
int q;
vector <ciuperca> h[auxmod];

ciuperca sch(long long a, long long b)
{
	ciuperca rez;
	rez.x = a;
	rez.y = b;
	return rez;
}

int ciup(long long x) 
{
    if(x<3)
		return x;

    int rest = x % auxmod, chestie;
    for(int i = 0; i<(int)h[rest].size(); i++)
	{
        if(h[rest][i].x==x)
			return h[rest][i].y;
    }
 
    if(x%2==1) 
	{
        chestie = (long long)ciup(x / 2) * ciup(x / 2) % mod;
    }
	else
	{
        chestie = (long long)ciup(x / 2) * ciup(x / 2 - 1) * 2 % mod;
    }

    h[rest].push_back(sch(x, chestie));

    return chestie;
}

int main(){
	int player_unu=0;
	freopen("ciuperci.in", "r", stdin);
	freopen("ciuperci.out", "w", stdout);
    scanf("%d", &q);
	
    for (int shp = 0; shp<q; shp++)
	{
        long long x;
		scanf("%lld", &x);
 
        for(int i = 0; i<auxmod; i++)
			h[i].clear();

        printf("%d\n", ciup(x));
    }
 
    return player_unu;
}