#include<iostream>
#include<fstream>
#define INF 40000
#define MOD 666013
using namespace std;
// T[2k]=2*T[k-1]*T[k];
// T[2k+1]=T[k]*T[k];

long long m,t,i;
long Pre[INF+69];

long long solve ( long long ind )
{
    if ( ind < INF)
        return Pre[ind];

    long long k;
    if ( ind%2 == 0 )
    {
        k=solve(ind/2);
        k=k*2%MOD;
        k=(k*solve(ind/2-1))%MOD;
        return k;
    }
    else{
        k=solve ( ind/2 );
        k=(k*k)%MOD;
        return k;
    }
}
int main()
{
    ifstream in("ciuperci.in");
    ofstream out("ciuperci.out");
    in>>t;
    Pre[1]=1;
    Pre[2]=2;
    long long k;
    for ( i=3; i<=INF; ++i)
    {
        if ( i%2==0)
        {
            k=Pre[i/2];
            k=k*2%MOD;
            k=(k*Pre[i/2-1])%MOD;
            Pre[i]=k;
        }
        else{
            k=Pre[i/2];
            k=(k*k)%MOD;
            Pre[i]=k;
        }
    }
    for ( ; t; --t )
    {
        in>>m;
        out<<solve (m)<<"\n";
    }
    return 0;
}