#include <fstream>
#include <utility>
#include <vector>
using namespace std;
#define Mod 666013
#define key first
#define value second

class Hash {
    public:
        void Insert(long long key,int value) {
            H[h(key)].push_back(make_pair(key,value));
        }

        void Clear() {
            for (int i = 0; i <= Modulo; i++)
                H[i].clear();
        }

        int getVal(long long key) {
            for (auto i: H[h(key)])
                if (i.key == key) return i.value;
            return -1;
        }

    private:
        static const long long Modulo = 997;
        vector< pair<long long,int> > H[Modulo+5];

        int h(int x) {
            return x & Modulo;
        }
};

Hash 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;

    int x = H.getVal(N);
    if (x != -1) return x;

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

    H.Insert(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";
    }
}