#include <fstream>
#include <map>
#include <unordered_map>
#define MOD 666013
#define NMAX int(1e8)

using namespace std;

/********************************/
/// INPUT / OUTPUT

ifstream f("ciuperci.in");
ofstream g("ciuperci.out");
/********************************/
/// GLOBAL DECLARATIONS

long long N, Q;
int num[NMAX];
/********************************/
/// FUNCTIONS

void ReadInput();
void Solution();
/********************************/
///------------------------------------------
inline void ReadInput()
{
    f >> Q;
}
///------------------------------------------
int Solve(long long size)
{
    if (size == 1)
        return 1;
    if (size == 2)
        return 2;
    
    if (size < 1e8 && num[size] != 0)
        return num[size];
    
    size --;
    int ans = Solve(size / 2);

    if (size & 1)
        ans = 2LL * ans * Solve(size / 2 + 1) % MOD;
    else
        ans = 1LL * ans * ans % MOD;
    
    if (size < 1e8) num[size + 1] = ans;
    return ans;

}
///------------------------------------------
inline void Solution()
{
    while (Q --)
    {
        f >> N;
        g << Solve(N) << "\n";
    }
}
///------------------------------------------
int main()
{
    ReadInput();
    Solution();
    return 0;
}