#include <fstream>

using namespace std;
long long q,k,i,j,x,w[1005],d[1005];
int main()
{
    ifstream f("ciuperci.in");
    ofstream g("ciuperci.out");
    f>>q;
    while(q)
    {
        q--;
        k=1;
        f>>w[k];
        i=1;
        while(w[k]>1)
        {
            if(w[i]%2==1)
            {
                x=w[i]/2;
                if(w[k]!=x)
                {
                    k++;
                    w[k]=x;
                }
            }
            else if(w[i]%2==0)
            {
                x=w[i]/2;
                if(w[k]!=x)
                {
                    k++;
                    w[k]=x;
                }
                x--;
                if(w[k]!=x)
                {
                    k++;
                    w[k]=x;
                }
            }
            i++;
        }
        k++;
        for(i=k; i>=1; i--)
        {
            if(w[i]<2) d[i]=1;
            else
            {
                if(w[i]%2) d[i]=1;
                else d[i]=2;
                x=w[i]/2;
                j=i;
                while(w[j]>x) j++;
                d[i]*=d[j];
                x=(w[i]-1)/2;
                while(w[j]>x) j++;
                d[i]*=d[j];
                d[i]%=666013;
            }
        }
        g<<d[1]<<'\n';
        for(i=1; i<=k; i++) d[i]=0;
        for(i=1; i<=k; i++) w[i]=0;
    }
    return 0;
}