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

using namespace std;

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

int MOD = 666013;
unordered_map <long long,long long> pam;

int Stuff(int ind);
int Functie(int n);

int Stuff(int ind){
    int val;
    if (pam.count(ind)) val = pam[ind];
    else{
        val = Functie(ind)%MOD;
        pam[ind] = val;
    }
    return val;
}

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

signed main()
{
    int t;
    fin >> t;
    while (t--){
        int n;
        fin >> n;
        fout << Functie(n) << '\n';
    }
    return 0;
}