#include <stdio.h>
#define MOD 666013
#include <vector>
#define DIM 8192

using namespace std;

struct par
{
    long long val;
    int res;
};

vector <par> H[35];

char ax[DIM+16];
int pz;

inline void cit(long long &x)
{
            x=0;
            while(ax[pz]<'0' || ax[pz]>'9')
                        if(++pz==DIM)fread(ax, 1, DIM, stdin), pz=0;
            while(ax[pz]>='0' && ax[pz]<='9')
            {
                        x=x*10+ax[pz]-'0';
                        if(++pz==DIM)fread(ax,1, DIM, stdin),pz=0;
            }
}

void AddHash (long long val, int x)
{
    int go = val & 31;
    par aux;
    aux.val = val; aux.res = x;
    H[go].push_back (aux);
}

int SearchHash (long long val)
{
    vector <par> :: iterator it;
    int go = val & 31;
    par aux;

    for (it = H[go].begin(); it != H[go].end (); it ++)
    {
        aux = *it;
        if (aux.val == val)
            return aux.res;
    }

    return 0;
}

int Solve (long long x)
{
    if (x == 0)
        return 1;
    if (x == 1)
        return 1;
    int val = SearchHash (x);
    if (val)
        return val;
    if (x & 1)
    {
        int X = Solve (x / 2), num;
        num = ((long long) X * X % MOD);
        AddHash (x, num);
        return num;
    }
    else
    {
        int num = (long long)Solve (x / 2) * Solve (x / 2 - 1) % MOD;
        num = num * 2 % MOD;
        AddHash (x, num);
        return num;
    }
}

int main ()
{
    long long x, Q, i;

    freopen ("ciuperci.in", "r", stdin);
    freopen ("ciuperci.out", "w", stdout);

    cit (Q);
    while (Q --)
    {
        for (i = 0; i <= 34; i ++)
            H[i].clear ();
        cit (x);
        printf ("%d\n", Solve (x));
    }

    return 0;
}