#include<cstdio>
#include<utility>
#include<algorithm>
using namespace std;
pair<long long,int> X[100005];
long long p2,P2,x;
int pm,i,Q,sol[100005];
int main()
{
    freopen("ciuperci.in","r",stdin);
    freopen("ciuperci.out","w",stdout);
    scanf("%d",&Q);
    for(i=1;i<=Q;i++)
    {
        scanf("%lld",&x);
        X[i]=make_pair(x,i);
    }
    sort(X+1,X+Q+1);
    p2=1;P2=2;pm=1;
    for(i=1;i<=Q;)
    {
        if(X[i].first>=P2){p2*=2;P2*=2;pm=(pm*2)%666013;continue;}
        sol[X[i].second]=pm;i++;
    }
    for(i=1;i<=Q;i++)printf("%d\n",sol[i]);
    return 0;
}