#include <cstdio>

#define Mod 666013

using namespace std;

long long Query (long long N)
{
    --N;
    if (N==0)
    {
        return 1;
    }
    if (N==1)
    {
        return 2;
    }
    if (N%2==0)
    {
        int S=Query (N/2);
        return (S*S)%Mod;
    }
    int SL=Query (N/2);
    int SR=Query (N/2+1);
    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 ("%d\n", Query (N));
    }
    /*freopen ("ciuperci.in", "w", stdout);
    printf ("100000\n");
    for (int i=1; i<=100000; ++i)
    {
        printf ("1000000000000\n");
    }*/
    return 0;
}