#include<stdio.h>
#include<assert.h>

#define ORLY 666013;

int t;
long long n;

long long f(long long x)
{
    if(x==0)
        return 1;
    if(x==1)
        return 2;
    if(x%2==0)
    {
        return f(x/2)*f(x/2)%ORLY;
    }
    else
        return 2*f(x/2)*f((x+1)/2)%ORLY;
}

void solve()
{
    assert(freopen("ciuperci.in","r",stdin)!=NULL);
    assert(freopen("ciuperci.out","w",stdout)!=NULL);
    int i;
    long long j;
    scanf("%d",&t);
    for(i=1;i<=t;++i)
    {
        scanf("%lld",&n);
        if(n==1)
        {
            printf("1\n");
            continue;
        }
        j=1;
        while(j<n)
        {
            n-=j;
            j*=2;

        }
        printf("%lld\n",f(n));
    }
}

int main()
{
    solve();
    return 0;
}