# include <cstdio>

using namespace std;

long long rez, n, a;


int ciup(int val)
{
   if (val == 1 || val == 0) return 1;
    
   if (val % 2 == 1) return ciup(val / 2) * ciup(val / 2);
                else return 2 * ciup(val / 2) * ciup(val / 2 - 1);
                 
}

int main()
{int i;
    
    freopen("ciuperci.in","r",stdin);
    freopen("ciuperci.out","w",stdout);
    
    scanf("%lld",&n);
    
    for (i = 1; i <= n; i++)
    {
        scanf("%lld",&a);
        
        rez = ciup(a);
                  
        printf("%lld\n",rez % 666013);
        }
        
return 0;
}