#include<iostream>
#include<vector>
#include<map>
using namespace std;
int lim = 1000000;
int stop = 0;
vector <int> v(1000000000/6);
int C(int,int);
void f()
{
v[1] = 3;
for (int i = 2; i < v.size(); i++)
v[i] = (2+3*v[i-1]) %lim;
}
int main()
{
int n,k;
cin >> n;
f();
for(int i = 0; i < n; i++)
{
cin >> k;
if (k != 0 && k%3==0 )
cout << v[k/3] <<" " ;
else cout << 0 << endl;
//cout << C(k,k) <<endl;
}
return 0;
}
int C(int el, int field)
{
if (field == 3) return 3;
return (2 + ( 3*C(el-3, field-3) )%lim ) ;
}
I2luY2x1ZGU8aW9zdHJlYW0+CiNpbmNsdWRlPHZlY3Rvcj4KI2luY2x1ZGU8bWFwPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmludCBsaW0gPSAxMDAwMDAwOwppbnQgc3RvcCA9IDA7CnZlY3RvciA8aW50PiB2KDEwMDAwMDAwMDAvNik7CgppbnQgQyhpbnQsaW50KTsKCnZvaWQgZigpCnsKCXZbMV0gPSAzOwoJZm9yIChpbnQgaSA9IDI7IGkgPCB2LnNpemUoKTsgaSsrKQoJCXZbaV0gPSAoMiszKnZbaS0xXSkgJWxpbTsKfQoKCgppbnQgbWFpbigpCnsKCWludCBuLGs7CgljaW4gPj4gbjsKCWYoKTsKCWZvcihpbnQgaSA9IDA7IGkgPCBuOyBpKyspCgl7CgkJY2luID4+IGs7CgkJaWYgKGsgIT0gMCAmJiBrJTM9PTAgKQoJCWNvdXQgPDwgdltrLzNdIDw8IiAiIDsKCQllbHNlIGNvdXQgPDwgMCA8PCBlbmRsOwoJCS8vY291dCA8PCBDKGssaykgPDxlbmRsOwoJCQoJfQogICAgcmV0dXJuIDA7Cn0KCmludCBDKGludCBlbCwgaW50IGZpZWxkKQp7CglpZiAoZmllbGQgPT0gMykgcmV0dXJuIDM7CglyZXR1cm4gKDIgKyAoIDMqQyhlbC0zLCBmaWVsZC0zKSApJWxpbSApIDsKfQoKCgoKCgoKCgo=