#include<stdio.h>
#include<vector>
#define mod 666013
#define mod2 32
using namespace std;
struct str
{
    long long ans,key;
    str(long long  anss,long long keyy)
    {
        key=keyy;
        ans=anss;
    }
};
vector<str> v[mod2+1];
int  query(long long k)
{
    if(k<=2)
        return k;
    int x=k%mod2;
    for(int i=0;i<v[x].size();i++)
    {
        if(v[x][i].key==k)
            return v[x][i].ans;
    }
    long long  q1=query(k/2);
    long long sol;
    if(k%2==1)
    {
       sol=((long long)q1*q1)%mod;

    }
    else
    {
         long long q2=2*query(k/2-1);
         sol=((long long ) q1*q2)%mod;
    }
    v[x].push_back(str(sol,k));
    return sol;

}
int main()
{
    long long  i,n,x;
    freopen("ciuperci.in","r",stdin);
    freopen("ciuperci.out","w",stdout);
    scanf("%lld",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%lld",&x);
        for(int j=0;j<=32;j++)
            v[j].clear();
        printf("%lld\n",query(x));
    }
    return 0;
}