#include <algorithm>
#include <cstdio>
#define PII pair<long long, long long>
#define x first
#define y second

using namespace std;

const int MOD=666013;

PII solve(long long m, long long n)
{
    if(m==0&&n==1) return make_pair(1LL, 1LL);
    if(m==1&&n==2) return make_pair(1LL, 2LL);
    PII a=solve(n/2-1, n/2), ret;
    if(n%2==0)
    {
        ret.x=a.x*a.x%MOD;
        ret.y=a.x*a.y*2%MOD;
    }
    else
    {
        ret.y=a.y*a.y%MOD;
        ret.x=a.x*a.y*2%MOD;
    }
    return ret;
}

int main()
{
    freopen("ciuperci.in", "r", stdin);
    freopen("ciuperci.out", "w", stdout);
    int q;
    long long n;
    PII sol;
    scanf("%d", &q);
    while(q--)
    {
        scanf("%lld", &n);
        sol=solve(n-1, n);
        printf("%lld\n", sol.y);
    }
}