#include <bits/stdc++.h>

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

using ll = long long;
/// (n - 1) par
/// dp[n] = dp[(n - 1) / 2] ^ 2
/// (n - 1) impar
/// dp[n] = 2 * dp[(n - 1) / 2] dp[(n - 1) / 2 + 1]

inline void solve(ll n, ll &cur, ll &nxt)
{
    if(n == 0)
    {
        cur = 1;
        nxt = 1;
        return;
    }
    if(n == 1)
    {
        cur = 1;
        nxt = 2;
        return;
    }
    ll axCur, axNxt;
    solve(((n - 1) >> 1), axCur, axNxt);
    if((n - 1) % 2 == 0)
    {
        cur = axCur * axCur % MOD;
        nxt = 2 * axNxt * axCur % MOD;
    }
    else
    {
        cur = 2 * axNxt * axCur % MOD;
        nxt = axNxt * axNxt % MOD;
    }
}


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

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