#include <fstream>
#include <vector>
using namespace std;
ifstream in("ciuperci.in");
ofstream out("ciuperci.out");

struct ciuperca{
    long long x, y;
};

const int mod= 666013, auxmod = 63;
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;
    in>>q;
    for (int shp = 0; shp<q; shp++)
	{
        long long x;
        in>>x;
 
        for(int i = 0; i<auxmod; i++)
			h[i].clear();

        out<<ciup(x)<<"\n";
    }
 
    return player_unu;
}