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

#define ORLY 666013;

int t;
long long n,p;

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

int f(int  x)
{
    if(x<2)
        return 1;
    if(x%2==0)
    {
        p=2*f((x-1)/2+1)*f((x-1)/2);
        return p%ORLY;
    }
    p=f((x-1)/2);
    p*=p;
    return 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;
        }
        n%=ORLY;
        printf("%d\n",f(n));
    }
}

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