#include <cstdio>

#define Mod 666013

using namespace std;

int Query (long long N)
{
    if (N<=2) return N;
    if (N&1)
    {
        int S=Query ((N-1)/2);
        return (1LL*S*S)%Mod;
    }
    int SL=Query ((N-1)/2);
    int SR=Query ((N-1)/2+1);
    return (1LL*2*SL*SR)%Mod;
}

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