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

int T;
LL N;

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 = 2, put2 = 2;

         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)put1 * put1) % mod;
              N = N / 2;

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

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

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

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

         sol = ((LL)sol * put1) % mod;

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

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

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

                   sol = ((LL)sol * put1) % mod;

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

                   sol = ((LL)sol * put2) % mod;

                   LL aux = ((LL)put1 * put2) % mod;
                   aux = ((LL)aux * put1) % mod;
                   put1 = aux;
              }

              j1 = nj1, j2 = nj2;
         }

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

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