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

using namespace std;

struct el
{
    long long val;
    int rez;
};
vector <el> H[MOD];

inline void AddHash(el w)
{
    int key=w.val%MOD;
    H[key].push_back(w);
}

inline int SearchHash(long long x)
{
    int key=x%MOD;
    vector <el>::iterator it;
    for(it=H[key].begin();it!=H[key].end();++it)
        if(it->val==x)
            return it->rez;
    return -1;
}

inline int Solve(long long x)
{
    int aux=SearchHash(x);
    el w;
    if(aux!=-1) return aux;
    if(x<=1) return 1;
    --x;
    if(x%2==0)
    {
        aux=(1LL*Solve(x/2)*Solve(x/2))%mod;
        w.val=x+1; w.rez=aux;
        AddHash(w);
        return aux;
    }
    aux=(2LL*Solve(x/2)*Solve(x/2+1))%mod;
    w.val=x+1; w.rez=aux;
    AddHash(w);
    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;
}