#include <fstream>
#define MOD 666013

using namespace std;

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

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

long long N, Q;
/*********************************/
/// FUNCTIONS

void ReadInput();
void Solution();
/*********************************/
///-------------------------------------------
inline void ReadInput()
{
    f >> Q;
}
///-------------------------------------------
int Solve(long long N, int ctx, int cty, int pow)
{
    if (N == 0)
        return pow;
    
    if (N % 2 == 1)
    {
        ctx = 2 * ctx + cty;
        pow += cty;
    }
    else
    {
        cty = 2 * cty + ctx;
        pow += ctx;
    }

    return Solve((N - 1) / 2, ctx, cty, pow);
}
///-------------------------------------------
long long Put(int pow)
{
    long long ans = 1;
    long long exp = 2;

    while (pow)
    {
        if (pow % 2 == 1)
        {
            ans *= exp;
            ans %= MOD;
        }
        exp *= exp;
        exp %= MOD;
        pow /= 2;
        
    }
    return ans;
}
///-------------------------------------------
inline void Solution()
{
    while (Q --)
    {
        f >> N;
        g << Put(Solve(N, 1, 0, 0)) << "\n";
    }
    
}
///-------------------------------------------
int main()
{
    ReadInput();
    Solution();
}