#include <bits/stdc++.h>
#define int long long
#define mod 666013
using namespace std;

ifstream f("ciuperci.in");
ofstream g("ciuperci.out");

map<int,bool> is;
unordered_map<int,int> val;
void solve()
{
    is.clear();
    val.clear();
    queue<int> q;
    int n; f>>n;
    q.push(n);
    is[n]=1;
    while(!q.empty())
    {
        int c=q.front();
        q.pop();
        if(c==1) continue;
        int next=(c-1)>>1;
        if(next!=0&&is.find(next)==is.end()) {is[next]=1; q.push(next);}
        if(c%2==0&&is.find(next+1)==is.end()) {is[next+1]=1; q.push(next+1);}
    }
    val[0]=1;
    for(auto e:is)
    {
        int v=e.first;
        if(v==1)
        {
            val[v]=1;
        }
        else if (v%2==1)
        {
            int a=val[(v-1)>>1];
            val[v]=(a*a)%mod;
        }
        else
        {
            int nxt=(v-1)>>1;
            val[v]=(val[nxt]*val[nxt+1]*2)%mod;
        }
        //g<<v<<','<<val[v]<<'\n';
    }
    g<<val[n]<<'\n';
}

int32_t main()
{
    int t=1;
    f>>t;
    while(t--)
    {
        solve();
    }
    return 0;
}