#include <bits/stdc++.h>
 
const long long MOD = 666013;
std::pair <int, int> D(long long n){
    if(n == 0) return {1, 1};
    if(n == 1) return {1, 2};
    if(n % 2){
        std::pair <int, int> ans = D(n / 2);
        return {(1LL * ans.first * ans.first) % MOD, (2LL * ans.first * ans.second) % MOD};
    }
    else{
        std::pair <int, int> ans = D(n / 2 - 1);
        return {(2LL * ans.first * ans.second) % MOD, (1LL * ans.second * ans.second) % MOD};
    }
}
 
int main(){
    FILE*fi,*fo;
    fi = fopen("ciuperci.in","r");
    fo = fopen("ciuperci.out","w");
 
    int n;
    fscanf(fi,"%d", &n);
    for(int i = 1; i <= n; i++){
        long long x;
        fscanf(fi,"%lld", &x);
        fprintf(fo,"%d\n", D(x).first);
    }
 
    return 0;
}