#include <cstdio>

const long long MOD = 666013;
long long N, M, K, sol;
int Q;

long long plasare( long long m, long long n ){
    if( m == 1 )
        return n;
    if( n - m == 1 )
        return n;
    if( m == n )
        return 1;
    if( m % 2 == 0 )
    {
        long long sol = plasare( m / 2, n / 2 );
        return ( sol * sol ) % MOD;
    }

    long long sol1 = plasare( m / 2, n / 2 ), sol2 = plasare( m / 2 - 1, n / 2 );
    return ( 2 * ( sol1 * sol2 ) % MOD ) % MOD;
}

long long log( long long N ){
    int i = 0;
    while( 1 << i < N )
        i ++;
    if( 1 << i == N )
        return i;
    return i - 1;
}

int main(){

    freopen( "ciuperci.in", "r", stdin );
    freopen( "ciuperci.out", "w", stdout );

    scanf( "%d", &Q );
    for( ; Q; Q-- ){
        scanf( "%lld", &N );
        K = log( N );
        M = N -  ( 1 << K ) + 1;
        sol = plasare( M, 1 << K );
        printf( "%lld\n", plasare( M, 1 << K ) );
    }

    fclose( stdin );
    fclose( stdout );
    return 0;
}