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

#define MOD 666013
#define MAX 10005
#define DIM 127

vector <pair <long long,int> > h[DIM+5];
long long N;
int T;

char buff[MAX];
int poz=MAX-1;

inline void cit (long long &nr)
{
    for ( ; !isdigit (buff[poz]); )
        if (++poz==MAX)
        {
            fread (buff,1,MAX,stdin);
            poz=0;
        }
    for (nr=0; isdigit (buff[poz]); )
    {
        nr=nr*10+buff[poz]-'0';
        if (++poz==MAX)
        {
            fread (buff,1,MAX,stdin);
            poz=0;
        }
    }
}

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,(int)(nr&DIM));
    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[(int)(nr&DIM)].push_back (make_pair (nr,rez));
    }

    return rez;
}

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

    scanf ("%d\n",&T);
    for (int i=0; i<T; ++i)
    {
        cit (N);
        for (int j=0; j<DIM; ++j)
            h[j].clear ();
        printf ("%d\n",solve (N));
    }

    return 0;
}