#include <fstream>
#include <map>

using namespace std;

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

long long MOD = 666013;

map<long long, long long> memo;

long long Functie(long long n){
    if (n==0 or n==1){
        return 1;
    }
    if (memo.count(n)){
        return memo[n];
    }
    long long rez;
    if (n % 2 ==1){
        long long val = Functie(n/2)%MOD;
        rez = val*val%MOD;
    }else{
        rez = Functie(n/2)*Functie(n/2-1)%MOD*2%MOD;
    }
    return memo[n] = rez;
}

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