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

unordered_map<long long, int> H;

int Solve(long long N)         // number of ways to build a binary tree with N nodes
{
    if (N == 1) return 1;
    if (N == 2) return 2;

    if (H.find(N) != H.end())
        return H[N];

    N--;                         // substract root
    int x = Solve(N/2);
    if (N&1LL)
        x = 2LL * x * Solve(N/2+1) % Mod;
    else x = 1LL * x * x % Mod;

    H[N+1] = x;
    return x;
}

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

    long long N;
    int t;

    fin >> t;
    while (t--)
    {
        H.clear();
        fin >> N;
        fout << Solve(N) << "\n";
    }
}