#include<iostream>
#include<cstdio>
#include<utility>
#include<algorithm>
using namespace std;
int i,n,p2[70];
long long P2[70],x;
int main()
{
    freopen("ciuperci.in","r",stdin);
    freopen("ciuperci.out","w",stdout);
    P2[0]=1;p2[0]=1;
    for(i=1;i<=64;i++)
    {
        p2[i]=(2*p2[i-1])%666013;
        P2[i]=2*P2[i-1];
    }
    cin>>n;
    for(;n;n--)
    {
        cin>>x;
        for(i=0;;i++)if(P2[i]>x)break;
        cout<<p2[i-1]<<'\n';
    }
    return 0;
}