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