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