# include <cstdio>

using namespace std;

long long rez[1000000], a;
int n;
int main()
{int i;
    
    freopen("ciuperci.in","r",stdin);
    freopen("ciuperci.out","w",stdout);
    
    scanf("%d",&n);
    
    rez[0] = 1; rez[1] = 1;
    for (i = 1; i <= n; i++)
    {
        scanf("%lld",&a);
        if (a % 2 == 0)
                       rez[a] = 2 * rez[a / 2] * rez[a / 2 - 1];
                  else rez[a] = rez[a / 2] * rez[a / 2];
                  
        printf("%lld\n",rez[a] % 666013);
        }
        
return 0;
}