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

#define MOD 666013
#define DIM 9007

vector <pair <long long,int> > h[MOD];
int T,N;

inline int find (long long nr,int poz)
{
    for (vector <pair <long long,int> > :: iterator it=h[poz].begin (); it!=h[poz].end (); ++it)
        if (it->first==nr)
            return it->second;

    return 0;
}

inline int solve (long long nr)
{
    if (nr<=1)
        return 1;

    int rez=find (nr,nr%MOD);
    if (!rez)
    {
        rez=solve (nr>>1);

        if (nr&1)
            rez=(1LL*rez*rez)%MOD;
        else
            rez=(1LL*2*rez*solve ((nr>>1)-1))%MOD;
        h[nr%MOD].push_back (make_pair (nr,rez));
    }

    return rez;
}

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

    scanf ("%d",&T);
    for (int i=0; i<T; ++i)
    {
        scanf ("%d",&N);
        printf ("%d\n",solve (N));
    }

    return 0;
}