#include <bits/stdc++.h>

#define MOD 666013
using namespace std;
ifstream fin("ciuperci.in");
ofstream fout("ciuperci.out");

using ll = long long;

inline ll solve(ll n){
    if(n <= 2)
        return n;
    if((n - 1) % 2 == 0){
        ll val = solve((n - 1) >> 1);
        return val * val % MOD;
    }
    return 2 * solve((n - 1) >> 1) * solve((n - 1) - ((n - 1) >> 1)) % MOD;
}

int main()
{
    int t;
    fin >> t;

    while(t--){
        ll n;
        fin >> n;
        fout << solve(n) << '\n';
    }
    return 0;
}