# include <cstdio>

using namespace std;

long long rez, a;
int n;

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

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