#include <cstdio>

#define modulo 666013

void solve(long long A, long long B, long long &R1, long long &R2)
{
     long long t1, t2;
     long long P[4];
     
     if (A < 2 && B < 2) { R1 = R2 = 1; return; }
     
     --A;
     --B;
     P[0] = A/2;
     P[1] = A-P[0];
     P[2] = B/2;
     P[3] = B-P[2];
     
     solve(P[0], P[3], t1, t2);
     
      if (P[0] == P[1]) R1 = (t1*t1) % modulo;
         else R1 = (t1*t2*2)%modulo;
      if (P[2] == P[3]) R2 = (t2*t2) % modulo;
         else R2 = (t1*t2*2) % modulo;
}

int main()
{
    int Q;
    long long R1, R2, N;
    
    freopen("ciuperci.in","r",stdin);
    freopen("ciuperci.out","w",stdout);
    
    scanf("%d", &Q);
    while (Q--)
    {
          scanf("%lld", &N);
          --N;
          solve(N/2, N-N/2, R1, R2);
          if ((N&1) == 0) printf("%lld\n", (R1*R2)%modulo);
             else printf("%lld\n", (R1*R2*2)%modulo);
    }
    
    return 0;
}