#include <stdio.h>
 
#define MOD 666013
#define MAXLOG 60
 
long long Aux, N, Ans, putere, K;
int T;
int i, nr, x;
long long put2[MAXLOG];
 
int main()
{
    freopen("ciuperci.in","r",stdin);
    freopen("ciuperci.out","w",stdout);
     
    scanf("%d",&T);
     
    put2[0] = 1LL;
    for (i=1; i<MAXLOG; ++i)
        put2[i] = put2[i-1] * 2;
     
    for (; T; --T){
        scanf("%lld",&N);
         
        Aux = 1LL; nr = 0;
        while (Aux <= N){
            N-= Aux;
            Aux = Aux*2;
            ++nr;
        }
         
        K = N; N = nr;
        putere = 0;
 
        while (K!=0 && N!=0){
             
            Aux = K-1;
            x = 0;
            while (Aux){
                ++x;
                Aux = Aux / 2;
            }
             
            putere = putere + (N-x)*K;
             
            N = x;
            K = put2[N] - K;
        }
         
        Ans = 1;
        Aux = 2;
        for (i = 0; put2[i] <= putere; ++i){
            if (putere & put2[i])
                Ans = (Ans * Aux) % MOD;
            Aux = (Aux * Aux) % MOD;
        }
         
        printf("%d\n", Ans);
    }
     
    return 0;
}