#include <fstream>
using namespace std;

const int N=250005,mod=666013;
int v[N];

ifstream in("ciuperci.in");
ofstream out("ciuperci.out");

inline long long sq(long long n)
{
    return n*n;
}

long long calc(long long n)
{
    if (n<N)
        return v[n];
    if (n&1)
        return sq(calc(n/2))%mod;
    return 2*calc(n/2)*calc(n/2+1)%mod;
}

int main()
{
    long long n,t;
    v[1]=1;v[2]=2;
    for (int i=3;i<N;i++)
        if (i&1)
            v[i]=v[i/2]*v[i/2];
        else
            v[i]=2*v[i/2]*v[i/2+1];
    in>>t;
    while (t--)
    {
        in>>n;
        out<<calc(n)<<"\n";
    }
    return 0;
}