#include <cstdio>
#include <vector>
#include <algorithm>

#define Mod 666013
#define x first
#define y second

using namespace std;

int T;
long long n;
vector < pair < long long, int > > Hash[32];

int solve(long long n){
    if(n == 1)
        return 1;
    if(n == 2)
        return 2;
    int poz = n & (32 - 1);
    for(int i = 0; i < Hash[poz].size(); ++i)
        if(Hash[poz][i].x == n)
            return Hash[poz][i].y;
    int Ans = 0;
    if(n & 1)
        Ans = (1LL * solve(n / 2) * solve(n / 2)) % Mod;
    else
        Ans = (1LL * 2 * solve((n - 1) / 2) * solve((n - 1) / 2 + 1)) % Mod;
    Hash[poz].push_back(make_pair(n, Ans));
    return Ans;
}

int main(){
    freopen("ciuperci.in", "r", stdin);
    freopen("ciuperci.out", "w", stdout);
    scanf("%d", &T);
    while(T){
        --T;
        scanf("%lld", &n);
        printf("%d\n", solve(n));
        for(int i = 0; i <= 31; ++i)
            Hash[i].clear();
    }
    return 0;
}