#include <fstream>

using namespace std;

ifstream fin ("ciuperci.in");
ofstream fout ("ciuperci.out");

const int mod = 666013;

int n;
int nr_noduri;

int modalitati(int n){
    if(n == 0){
        return 1;
    }
    if((n - 1) % 2 == 0){
        return modalitati((n-1)/2) * modalitati((n-1)/2) % mod;
    }
    long long a = modalitati((n-1)/2);
    long long b = modalitati((n-1)/2 + 1);
    return (2LL * a % mod * b) % mod;
}

int main(){
    fin >> n;
    for(int i = 1; i <= n; i++){
        fin >> nr_noduri;
        fout << modalitati(nr_noduri) <<'\n';
    }
    return 0;
}