#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define LL long long
#define mod 666013

int T;
LL N;

LL put(int a, LL X) {
    LL ret;

    if(X == 0) return 1;
    if(X == 1) return a;

    if(X % 2 == 0) {
         LL jeg = put(a, X/2);
         ret = ((LL)jeg * jeg) % mod;
    }
    else {
         LL jeg = put(a, X/2);
         ret = ((LL)a * jeg) % mod;
         ret = ((LL)ret * jeg) % mod;
    }

    return ret;
}

int main() {
    FILE *f1=fopen("ciuperci.in", "r"), *f2=fopen("ciuperci.out", "w");

    fscanf(f1, "%d\n", &T);
    while(T--) {
         fscanf(f1, "%lld\n", &N);

         LL sol = 1;
         LL put1 = 1, put2 = 1;

         if(N == 1 || N == 3) {
              fprintf(f2, "1\n");
              continue;
         }
         if(N == 2) {
              fprintf(f2, "2\n");
              continue;
         }

         int ok = 1;
         while(N % 2 == 1) {
              put1 = (LL)2 * put1;
              N = N / 2;

              if(N == 1) {
                   ok = 0;
                   break;
              }
         }

         if(!ok) {
              fprintf(f2, "1\n");
              continue;
         }

         if(N == 2) {
              sol = ((LL)put(2, put1)) % mod;
              fprintf(f2, "%lld\n", sol);
              continue;
         }

         //N = par
         LL j1 = N / 2 - 1;
         LL j2 = N / 2;
         put2 = put1;

         sol = ((LL)sol * put(2, put1)) % mod;

         while(j1 >= 1) {
              LL nj1, nj2;

              if(j1 == 1 && j2 == 2) {
                   sol = ((LL)sol * put(2, put2)) % mod;
                   break;
              }
              if(j1 == 2 && j2 == 3) {
                   sol = ((LL)sol * put(2, put1)) % mod;
                   break;
              }

              if(j1 % 2 == 0) {
                   nj1 = j1 / 2 - 1;
                   nj2 = j1 / 2;

                   sol = ((LL)sol * put(2, put1)) % mod;
                   put2 = (LL)3 * put2;
              }
              else {
                   nj1 = j1 / 2;
                   nj2 = j1 / 2 + 1;

                   sol = ((LL)sol * put(2, put2)) % mod;
                   put1 = (LL)3 * put1;
              }

              j1 = nj1, j2 = nj2;
         }

         fprintf(f2, "%lld\n", sol);
    }

    fclose(f1); fclose(f2);
    return 0;
}