#include <bits/stdc++.h>
#define LIM 1000000

const long long MOD = 666013;
long long d[1 + LIM];
long long D(long long n){
    if(n <= 1) return 1;
    if(n > LIM){
        if(n % 2) return (D(n / 2) * D(n / 2)) % MOD;
        else return (2 * D(n / 2) * D(n / 2 - 1)) % MOD;
    }
    if(d[n] != -1) return d[n];
    if(n % 2) d[n] = (D(n / 2) * D(n / 2)) % MOD;
    else d[n] = (2 * D(n / 2) * D(n / 2 - 1)) % MOD;
    return d[n];
}

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

    int n;
    fscanf(fi,"%d", &n);
    for(int i = 0; i <= LIM; i++) d[i] = -1;
    for(int i = 1; i <= n; i++){
        long long x;
        fscanf(fi,"%lld", &x);
        fprintf(fo,"%lld\n", D(x));
    }

    return 0;
}