#include <bits/stdc++.h>

using namespace std;

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

const int mod=666013;

long long solve(int nivel,long long noduri)
{
 if(noduri==0||nivel==1) return 1;

 if(noduri%2==1) return 2*solve(nivel-1,noduri/2)*solve(nivel-1,noduri-noduri/2)%mod;
 return solve(nivel-1,noduri/2)*solve(nivel-1,noduri-noduri/2)%mod;
}

int main()
{
 int teste;
 f>>teste;

 while(teste--)
 {
   long long x;
   f>>x;

   long long cpy=x,nivel=0;
   while(cpy!=0){
    cpy/=2;
    nivel++;
   }
   g<<solve(nivel,x - ( (1<<(nivel-1))-1 ) )<<'\n';
 }
}