#include<fstream>
using namespace std;
#define INF 32000
#define MOD 666013
// T[2*k+1]=T[k]*T[k];
// T[2*k]=T[k]*T[k-1]*2;
long pre[INF+5];
long i;
long long n,t;
long long k;
long long solve ( long long ind )
{
    long long k;
    if ( ind < INF)
        return pre[ind];
    if ( ind%2==1)
    {
        k=solve(ind/2);
        k=k*k%MOD;
        return k;
    }
    k=solve(ind/2);
    k=k*solve(ind/2-1)%MOD;
    k*=2;
    k%=MOD;
    return k;
}
int main()
{
    ifstream in("ciuperci.in");
    ofstream out("ciuperci.out");
    pre[1]=1;
    pre[2]=2;
    for ( i=3; i<INF; ++i)
    {
        if ( i%2==1 )
        {
            k=pre[i/2]*pre[i/2]%MOD;
            pre[i]=k;
        }
        else{
            k=2*pre[i/2]*pre[i/2-1]%MOD;
            pre[i]=k;
        }
    }
    in>>t;
    for ( ; t; --t)
    {
        in>>n;
        out<<solve (n)<<"\n";
    }
}