#include <fstream>

#define MOD 666013
#define Size 150000

using namespace std;

ifstream in;
ofstream out;

int v[Size];

inline int f(long long N)
{
    if(N<Size) return v[N];

    long long sol=0,aux,M;

    if(N&1)
    {
        M=N>>1;
        if(M<Size) aux=v[M];
        else
        if(M&1)
        {
            aux=f(M>>1);
            aux*=aux;
            aux%=MOD;
        }
        else
        {
            aux=((long long)((f((M>>1)-1)*f(M>>1))>>1));
            aux%=MOD;
        }

        sol=aux*aux;
    }
    else sol=((long long)((f((N>>1)-1)*f(N>>1))>>1));

    return sol%MOD;
}

int main()
{
    int Test;
    long long N;

    in.open("ciuperci.in");
    out.open("ciuperci.out");

    in>>Test;

    v[0]=1;
    v[1]=1;
    for(int i=2;i<Size;++i)
        if(i&1) v[i]=((long long)v[i>>1]*v[i>>1])%MOD;
        else v[i]=((long long)2*v[i>>1]*v[(i>>1)-1])%MOD;

    for(;Test--;)
    {
        in>>N;
        out<<f(N)<<'\n';
    }

    in.close();
    out.close();

    return 0;
}