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

#define MOD 666013
#define DIM 337

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

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 ()
{
    ifstream fin ("ciuperci.in");
    ofstream fout ("ciuperci.out");

    fin>>T;
    for (int i=0; i<T; ++i)
    {
        fin>>N;
        for (int j=0; j<DIM; ++j)
            h[j].clear ();
        fout<<solve (N)<<"\n";
    }

    return 0;
}