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

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

int exp(int a,int p)
{
    if(p==0) return 1;
    if(p==1) return a;
    if(p%2==0) return exp((a*a)%mod,p>>1);
    return (exp((a*a)%mod,p>>1)*a)%mod;

}

void solve()
{
    int n; f>>n;
    int p=0;
    for(int i=2;i-1<=n;i=i<<1)
    {
        int md=(n-i+1)%i;
        //g<<i<<','<<md<<','<<min(md,i-md)<<'\n';
        p+=min(md,i-md);
    }
    g<<exp(2,p)<<'\n';
}

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