#include<bits/stdc++.h>
#define MOD 666013
#define x first
#define y second
using namespace std;
ifstream fin("ciuperci.in");
ofstream fout("ciuperci.out");

typedef long long ll;

pair<ll , ll> solve(ll n)
{
    if(n==1)
        return {2, 1};
    if(n==2)
        return {1, 2};

    if(n&1)
    {
        pair<ll, ll> tmp = solve(n/2);
        return {(2LL * tmp.x * tmp.y)%MOD, (tmp.y * tmp.y)%MOD};
    }
    else
    {
        pair<ll, ll> tmp = solve(n/2-1);
        return {(tmp.x * tmp.x)%MOD, (2LL * tmp.x * tmp.y)%MOD};
    }
}

int main()
{
    ll T, n;
    fin >> T;
    while(T--)
    {
        fin >> n;
        fout << solve(n).y << '\n';
    }

    return 0;
}