#include <cstdio>
#include <vector>
#define mod 666013

using namespace std;

inline int Solve(long long x)
{
    if(x<=1) return 1;
    --x;
    int aux1=Solve(x/2),aux2=Solve(x/2+1),aux;
    if(x%2==0)
    {
        aux=(1LL*aux1*aux1)%mod;
        return aux;
    }
    aux=(2LL*aux1*aux2)%mod;
    return aux;
}

int main()
{
    int T;
    long long N;
    freopen ("ciuperci.in","r",stdin);
    freopen ("ciuperci.out","w",stdout);
    scanf("%d", &T);
    while(T--)
    {
        scanf("%lld", &N);
        printf("%d\n", Solve(N));
    }
    return 0;
}