#include <fstream>

#define MOD 666013
#define Size 500000

using namespace std;

ifstream in;
ofstream out;

int v[Size];

inline int f(long long N)
{
    long long sol=0,aux;

    if(N<Size) return v[N];
    else
    if(N&1)
    {
        aux=f(N>>1);
        sol+=aux*aux;
    }
    else
    {
        aux=2*f((N>>1)-1);
        aux*=f(N>>1);
        sol+=aux;
    }

    sol%=MOD;
    return sol;
}

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;
}