#include <cstdio>
#include <set>

using namespace std;

#define mod 666013

int t, n;
pair<int, int> per;

pair<int, int> solve(long long s1, long long s2)
{
    if(s1<2 && s2<2)
        return make_pair(1, 1);
    pair<int, int> x = solve((s1-1)/2, (s2-1)/2+(s2-1)%2);
    pair<int, int> rez;
    if(s1%2)
        rez.first=(1LL*x.first*x.first)%mod;
    else
        rez.first=(1LL*x.first*x.second*2)%mod;

    if(s2%2)
        rez.second=(1LL*x.second*x.second)%mod;
    else
        rez.second=(1LL*x.first*x.second*2)%mod;
    return rez;
}

int main()
{
    freopen("ciuperci.in", "r", stdin);
    freopen("ciuperci.out", "w", stdout);

    scanf("%d", &t);
    for(int i=1; i<=t; ++i)
    {
        scanf("%lld", &n);
        per=solve((n-1)/2, (n-1)/2+(n-1)%2);
        printf("%lld\n", (1LL*per.first*per.second*(2-n%2))%mod);
    }

    return 0;
}