#include <cstdio>
#include <cstdlib>
#include <vector>
using namespace std;
 
#define modulo 666013
#define pb push_back
#define mp make_pair
 
vector<pair<long long, int> > Hash[32];
int T;
long long Val;
 
 
int GetSol(long long N)
{
    if(N < 3) return N;
    int S = N & 31, A, B;
    vector<pair<long long, int> > :: iterator it;
    for(it = Hash[S].begin(); it != Hash[S].end(); ++it)
           if(it -> first == N)
                 return it -> second;
    if(N & 1)
    {
         A = GetSol(N >> 1);
         A = (1LL * A * A) % modulo;
         Hash[S].pb(mp(N, A));
         return A;
    }else
    {
         A = GetSol((N - 1) >> 1);
         B = GetSol(((N - 1) >> 1) + 1);
         A = (1LL * 2 * A * B) % modulo;
         Hash[S].pb(mp(N, A));
         return A;
    }
}
 
int main()
{
    freopen("ciuperci.in", "r", stdin);
    freopen("ciuperci.out", "w", stdout);
    int i;
    scanf("%i", &T);
    for(; T; T--)
    {
          scanf("%lld", &Val);
          printf("%i\n", GetSol(Val));
          for(i = 0; i < 32; i++) Hash[i].clear();
    }
    return 0;
}