#include <cstdio>

#define mod 666013
#define ll long long
using namespace std;
int q;
void read()
{
    freopen("ciuperci.in", "r", stdin);
    scanf("%d", &q);
}
void solve(ll n, ll &x, ll &y)
{
    if (n == 0)
    {
        x = 1;
        y = 1;
        return ;
    }
    if (n == 1)
    {
        x = 2;
        y = 1;
        return ;
    }
    if (n == 2)
    {
        x = 1;
        y = 2;
        return ;
    }
    if (n == 3)
    {
        x = 2;
        y = 1;
    }
    ll a, b;
    if (n & 1)
    {
        solve(n >> 1, a, b);
        y = (b * b * 1LL) % mod;
        x = (2 * a * b * 1LL) % mod;
    }else
    {
        solve((n >> 1) - 1, a, b);
        x = (a * a * 1LL) % mod;
        y = (2 * a * b * 1LL) % mod;
    }
}
void write()
{
    ll a, b, x;
    freopen("ciuperci.out", "w", stdout);
    while (q --)
    {
        scanf("%lld", &x);
        solve(x, a, b);
        printf("%lld\n", b);
    }
}
int main()
{
    read();
    write();
    return 0;
}