#include<stdio.h>
#include<assert.h>

#define ORLY 666013;

int t;
long long n,p;

long long f(long long x)
{
    if(x<=1)
        return 1;
    if(x%2==0)
        return 2*f((x-1)/2+1)*f((x-1)/2)%ORLY;
    p=f((x-1)/2);
    return p*p%ORLY;
}

void solve()
{
    assert(freopen("ciuperci.in","r",stdin)!=NULL);
    assert(freopen("ciuperci.out","w",stdout)!=NULL);
    int i;
    scanf("%d",&t);
    for(i=1;i<=t;++i)
    {
        scanf("%lld",&n);
        if(n==1)
        {
            printf("1\n");
            continue;
        }
        printf("%lld\n",f(n));
    }
}

int main()
{
    solve();
    return 0;
}