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

#define ORLY 666013;

int t,a[100100];
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(long long  x)
{
    if(x>100000)
    {
        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;
    }
    if(a[x])
        return a[x];
    if(x%2==0)
    {
        a[x]=(long long)2*f((x-1)/2+1)*f((x-1)/2)%ORLY;
        return a[x];
    }
     p=f((x-1)/2);
     a[x]=(long long)p*p%ORLY;
     return a[x];
}

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

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