#include <cstdio>

#define Mod 666013

using namespace std;

long long Query (long long L, long long R)
{
    int Mid=(L+R)/2;
    if (L==R)
    {
        return 1;
    }
    if (R-L==1)
    {
        return 2;
    }
    if ((L+R)%2==0)
    {
        int S=Query (L, Mid-1);
        return (S*S)%Mod;
    }
    int SL=Query (L, Mid-1);
    int SR=Query (Mid+1, R);
    return (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;
        scanf ("%lld", &N);
        printf ("%lld\n", Query (1, N));
    }
    return 0;
}