#include<stdio.h>

long long rec(long long x)
{
if(x==1||x==0)
    return 1;
    long long q=rec(x/2);
    if(x%2==0)
        return (q*rec(x/2-1)*2)%666013;
    else return (q*q)%666013;
}
long long N,x;
int main()
{
freopen("ciuperci.in","r",stdin);
freopen("ciuperci.out","w",stdout);
    scanf("%lld",&N);
        for(int i=1;i<=N;++i)
        {
            scanf("%lld",&x);
            printf("%lld\n",rec(x));
        }
}