#include <fstream>

#define MOD 666013

using namespace std;

ifstream in;
ofstream out;

inline int f(long long N)
{
    long long sol=0;
    for(int bit=16;bit>=0;--bit)
        if(sol==0&&(N&(1<<bit))) sol=1;
        else
        if(sol)
            if(N&(1<<bit))
            {
                sol*=sol;
                sol%=MOD;
            }
            else
            {
                sol<<=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;
}