#include <fstream>
#include <algorithm>
#include <vector>
#define M 666013

using namespace std;
vector <long long> l,v;
long long recursiv(long long n)
{
    long long x=(n-1)/2;
    long long y=n-1-x;
    if(n==1) return 1;
    if(n==2) return 2;
    if(binary_search(v.begin(),v.end(),n))
        return l[(lower_bound(v.begin(),v.end(),n))-v.begin()];
    if(x==y)
    {
        int a=(recursiv(x)*recursiv(y))%M;
        v.insert(upper_bound(l.begin(),l.end(),n)-l.begin()+v.begin(),n);
        l.insert(upper_bound(l.begin(),l.end(),n),a);
        return a;
    }
    if(x!=y)
    {

        int a=(2*recursiv(x)*recursiv(y))%M;
        v.insert(upper_bound(l.begin(),l.end(),n)-l.begin()+v.begin(),n);
        l.insert(upper_bound(l.begin(),l.end(),n),a);
        return a;
    }
    return 0;
}
int main()
{
    int q;
    long long n;
    ifstream fi("ciuperci.in");
    ofstream fo("ciuperci.out");
    fi>>q;
    for(;q>0;q--)
    {
        //v.clear(); l.clear();
        fi>>n;
        fo<<recursiv(n)<<"\n";
    }

    return 0;
}