#include <cstdio>
#include <vector>
#define ll (long long)
#define md 666013
FILE *f,*g;

int q,n=55;
long long v[60];
long long sol[60];

void pre()
{
    v[1] = 1;
    sol[1] = 1;
    for (int i = 2;i <= n;i++)
    {
        sol[i] = ll (ll sol[i-1]<<1) % md;
        v[i] = ll v[i-1]<<1;
    }
}

long long solve(long long value)
{
    int left, right, mid, ans;
    left = 1; right = n;

    while (left<=right)
    {
        mid = (left+right)>>1;
        if (v[mid] > value)
        {
            right = mid-1;
        }
        else
        {
            ans = mid;
            left = mid+1;
        }
    }

    return sol[ans];
}


int main()
{
    f=fopen("ciuperci.in","r");
    g=fopen("ciuperci.out","w");

    pre();
    fscanf(f,"%d",&q);

    while (q--)
    {
        long long x;
        fscanf(f,"%lld",&x);
        fprintf(g,"%lld\n",solve(x));
    }

    fclose(g);
    return 0;
}