/*  x = T(n+1), y = T(n)
    T(n) = nr de arbori super-ech cu n noduri
*/
#include<fstream>
#define ll long long
using namespace std;
ifstream f("ciuperci.in"); ofstream g("ciuperci.out");
const int MOD = 666013;
void calc(ll n, ll &x, ll &y)
{   if(n==0) {x=1; y=1; return;}
    else    if(n==1) {x=2; y=1; return;}
            else    if(n==2) {x=1; y=2; return;}
    ll t,s;
    if(n&1)
    {   calc(n>>1,t,s);
        x=2*t*s%MOD; y=s*s%MOD;
    }
    else
    {   calc((n>>1)-1,t,s);
        x=t*t%MOD; y=2*t*s%MOD;
    }
}
int main()
{   int Q;
    ll n, x, y;
    f>>Q;
    while(Q--) {f>>n; calc(n,x,y); g<<y<<'\n';}
    g.close(); return 0;
}