#include <fstream>
#define mod 666013
using namespace std;

long long T(const long long &n)
{
    if (n == 1) return 1;
    if (n == 2) return 2;

    if (n&1 == 0)
        return (T(n-1)*T(n-1)/4)%mod;
    else return (2*T(n/2)*T(n/2-1))%mod;
}

int main()
{
    ifstream in("ciuperci.in");
    ofstream out("ciuperci.out");

    int Q, i, N;
    in>>Q;
    for (i=0; i<Q; ++i)
    {
        in>>N;
        out<<T(N)<<"\n";
    }

    in.close(); out.close();
    return 0;
}