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

struct ciuperca{
    long long x, y;
};

const int mod= 666013, auxmod = 37;
int q;
vector <ciuperca> h[auxmod];
 
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;
    }

	ciuperca aux;
	aux.x = x;
	aux.y = chestie;
    h[rest].push_back(aux);

    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;
}