#include <cstdio>
#include <map>

#define Mod 666013
#define LL long long

using namespace std;

map <LL, int> H;

int Query (LL N)
{
    if (N<=2) return N;
    if (H.find (N)!=H.end ())
    {
        return H[N];
    }
    int S;
    if (N&1)
    {
        S=Query ((N-1)/2);
        S=(1LL*S*S)%Mod;
    }
    else
    {
        int SL=Query ((N-1)/2);
        int SR=Query ((N-1)/2+1);
        S=(1LL*2*SL*SR)%Mod;
    }
    H[N]=S;
    return S;
}

int main()
{
    freopen ("ciuperci.in", "r", stdin);
    freopen ("ciuperci.out", "w", stdout);
    int NQ;
    scanf ("%d", &NQ);
    for (; NQ>0; --NQ)
    {
        LL N=0;
        scanf ("%lld", &N);
        printf ("%d\n", Query (N));
    }
    return 0;
}