#include <fstream>
#define nmax 500000
#define M 66013
using namespace std;
int arb[500005];
int main()
{
    int i,x,y,q;
    long long n;
    long long s;
    ifstream fi("ciuperci.in");
    ofstream fo("ciuperci.out");
    arb[1]=1; arb[2]=2;
    for(i=3;i<=nmax;i++)
    {
        x=(i-1)/2;
        y=i-1-x;
        if(x==y) s=(arb[x]*arb[y])%M; else
        s=(2*arb[x]*arb[y])%M;
        arb[i]=s;
    }
    fi>>q;
    for(;q>0;q--)
    {
        fi>>n;
        if(n>nmax) fo<<"0\n"; else
        fo<<arb[n]<<"\n";
    }

    return 0;
}