#include <bits/stdc++.h>
#define int long long

using namespace std;

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

int MOD = 666013;

int Functie(int n){
    if (n==0 or n==1) return 1;
    if (n%2==1){
        int val = Functie(n/2)%MOD;
        return val*val%MOD;
    }else{
        return Functie(n/2)*Functie(n/2-1)%MOD*2%MOD;
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    fin.tie(NULL);
    fout.tie(NULL);
    int t;
    fin >> t;
    while (t--){
        int n;
        fin >> n;
        fout << Functie(n) << '\n';
    }
    return 0;
}