#include <fstream>
#include <map>
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];
map<long long,int> H;

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

    fin >> t;
    while (t--)
    {
        fin >> N;
        x = N;
        if (H.find(N) != H.end()) {
            fout << H[N] << "\n";
            continue;
        }
        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;
        }
        H[x] = Ans;
        fout << Ans << "\n";
    }
}