#include <fstream>

#define MOD 666013

using namespace std;

ifstream in;
ofstream out;

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

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

    sol%=MOD;
    return sol;
}

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

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

    in>>Test;

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

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

    return 0;
}