#include <fstream>
#define nmax 125000
#define M 66013
using namespace std;
long long arb[125005];
long long recursiv(long long n)
{
    long long x=(n-1)/2;
    long long y=n-1-x;
    if(x==y and (x>nmax or y>nmax)) return (recursiv(x)*recursiv(y))%M;
    if(x!=y and (x>nmax or y>nmax)) return (2*recursiv(x)*recursiv(y))%M;
    if(x==y) return (arb[x]*arb[y])%M;
    if(x!=y) return (2*arb[x]*arb[y])%M;
    return 0;
}
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<<recursiv(n)%M<<"\n"; else
        fo<<arb[n]<<"\n";
    }

    return 0;
}