#include<cstdio>
#include<algorithm>
#define MOD 666013
using namespace std;
pair<long long,long long> DivideEtImpera(long long n){
    pair<long long,long long> temp;
    if(n==1)
        return make_pair(2,1);
    if(n==2)
        return make_pair(1,2);
    if(n%2==1){
        temp=DivideEtImpera(n/2);
        return make_pair((2*temp.first*temp.second)%MOD,(temp.second*temp.second)%MOD);
    }
    else{
        temp=DivideEtImpera(n/2-1);
        return make_pair((temp.first*temp.first)%MOD,(2*temp.first*temp.second)%MOD);
    }
}
int main(){
    freopen("ciuperci.in","r",stdin);
    freopen("ciuperci.out","w",stdout);
    int tests,test;
    long long n;
    pair<long long,long long> answer;
    scanf("%d",&tests);
    for(test=1;test<=tests;test++){
        scanf("%lld",&n);
        answer=DivideEtImpera(n);
        printf("%lld\n",answer.second);
    }
    return 0;
}