#include <stdio.h>
#include <vector>

using namespace std;
#define MOD 13

long long N;
vector<long long> G[MOD];
vector<long long> G2[MOD];
inline long long find_value(long long x)
{  ;
      //if(x==602066)
    //prlong longf("%lld ",x);
    long long list = x % MOD;
    vector<long long>::iterator it;
    vector<long long>::iterator it2;
    for (it = G[list].begin(),it2=G2[list].begin(); it != G[list].end(); ++it,++it2)
        {
        if (*it == x)
        {

            return *it2;
        }
        }
    return -1;
}

inline void insert_value(long long x,long long q)
{
    long long list = x % MOD;

        G[list].push_back(x);
        G2[list].push_back(q%666013);
}
long long rec(long long x)
{
if(x==1||x==0)
    return 1;
 //  printf("%lld==",x);
    long long w=find_value(x);
        if(w!=-1)
        {
       //  printf("!");
            return w;
        }
   //printf("%lld!\n",x);
    //long long w=rec(x/2-1);

    if(x%2==0)
        {
        long long q=rec(x/2);
        long long w=rec(x/2-1);
        insert_value(x,q*w*2%666013);
        return (q*w*2%666013);

        }
    else {
     long long q=rec(x/2);
    insert_value(x,q*q%666013);
    return (q*q)%666013;
    }
}
long long x;
int main()
{
freopen("ciuperci.in","r",stdin);
freopen("ciuperci.out","w",stdout);


    scanf("%lld",&N);
  // N=1;
        for(long long i=1;i<=N;++i)
        {
            scanf("%lld",&x);
            printf("%lld\n",rec(x));
        }
      //  printf("%lld",find_value(10101010101010));
}