#include <fstream>
using namespace std;
#define Mod 666013

long long N,M,R,pow;
int t,k;
long long Ans,x;

int Solve(long long N,long long M)
{
    if (M == 1) return N % Mod;
    x = Solve(N>>1LL,M>>1LL);
    if (M&1LL)
        return x * Solve(N>>1LL,(M>>1LL)+1) * 2 % Mod;
    return x*x%Mod;
}

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

    fin >> t;
    while (t--)
    {
        fin >> N;
        k = 0;
        while ((1LL<<k+1)-1 < N) ++k;
        M = (1LL<<k) - (1LL<<k+1) + 1 + N;
        fout << Solve(1LL<<k,M) << "\n";
    }
}


/*#include <fstream>
#include <stack>
using namespace std;
#define Mod 666013

long long N,M;
int t,k;
long long Ans,x;

struct Step {
    long long N,M;
    Step() { N = M = 0;};
};

int Size = 0;
Step ST[1000];

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

    fin >> t;
    while (t--)
    {
        fin >> N;
        k = 0;
        while ((1LL<<k+1)-1 < N) ++k;
        M = (1LL<<k) - (1LL<<k+1) + 1 + N;
//        fout << Solve(1LL<<k,M) << " ";
        Size = 1;
        ST[1].N = 1LL<<k;
        ST[1].M = M;
        Ans = 1;
        while (Size != 0)
        {
            if (ST[Size].M == 1) {
                Ans = Ans * ST[Size].N % Mod;
                Size--;
                continue;
            }
            if (ST[Size].M&1LL) Ans = Ans * 2 % Mod;
            M = ST[Size].M;
            N = ST[Size].N;
            Size--;
            ST[++Size].M = M / 2 + M % 2;
            ST[Size].N = N / 2;
            ST[++Size].M = M / 2;
            ST[Size].N = N / 2;
        }

        fout << Ans << "\n";
    }
}
*/