#include<iostream>
#include<stdio.h>
#include<fstream>
#include<vector>
using namespace std;
 
#define MOD 666013
#define MOD2 181
#define DIM 10000
#define mp make_pair
#define pb push_back
typedef pair < long long, int > PLLI;
 
vector < pair < long long, int > > v[MOD2];
int poz;
char buff[DIM];
 
inline int cauta(long long x)
{
    int k;
    k=x%MOD2;
    for(vector <PLLI> :: iterator it=v[k].begin();it!=v[k].end();it++)
        if(it->first == x)
            return it->second;
    return -1;
}
 
inline void adauga(PLLI x)
{
    v[x.first%MOD2].pb(x);
}
 
int calc(long long n)
{
    if(n==1 || n==0)
        return 1;
    if(n==2)
        return 2;
    int cnt;
    cnt=cauta(n);
    if(cnt!=-1)
        return cnt;
    if((n&1)==0) {
        long long k;
        int nr1,nr2,sol;
        k=(n-2)>>1;
        nr1=calc(k);
        nr2=calc(k+1);
        sol=(2LL*nr1*nr2)%MOD;
        adauga(mp(n,sol));
        return sol;
    }
    int nr,sol;
    nr=calc((n-1)>>1);
    sol=(1LL*nr*nr)%MOD;
    adauga(mp(n,sol));
    return sol;
}
 
void citeste(long long &numar)
{
    while(buff[poz]<'0' || buff[poz]>'9')
        if(++poz==DIM) {
            fread(buff,1,DIM,stdin);
            poz=0;
        }
    numar=0;
    while(buff[poz]>='0' && buff[poz]<='9') {
        numar=numar*10LL+buff[poz]-'0';
        if(++poz==DIM) {
            fread(buff,1,DIM,stdin);
            poz=0;
        }
    }
}
 
int main ()
{
    int i,j;
    long long n,q;
    freopen("ciuperci.in","r",stdin);
    freopen("ciuperci.out","w",stdout);
    citeste(q);
    for(i=1;i<=q;i++) {
        citeste(n);
        printf("%d\n",calc(n));
        for(j=0;j<=MOD2-1;j++)
            v[j].clear();
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}