#include <iostream>
#include <vector>
#define MOD 1000000
typedef long long ll;
using namespace std;

vector<vector<ll>> multiply(vector<vector<ll>> v1) {
	ll x00 = v1[0][0];
	ll x01 = v1[0][1];
	ll x10 = v1[1][0];
	ll x11 = v1[1][1];
	ll res00, res01, res10, res11;
	res00 = ((x00 * x00) % MOD + (x10 * x01) % MOD) % MOD;
	res01 = ((x00 * x01) % MOD + (x01 * x11) % MOD) % MOD;
	res10 = ((x10 * x00) % MOD + (x10 * x11) % MOD) % MOD;
	res11 = ((x10 * x01) % MOD + (x11 * x11) % MOD) % MOD;
	return{ {(res00 + MOD) % MOD, (res01 - MOD) % MOD}, {(res10 + MOD) % MOD, (res11 - MOD) % MOD} };
}
vector<vector<ll>> pow_mod(vector<vector<ll>> v, int p) {

	if (p == 1) return v;
	if ((p % 2) == 0) {
		vector<vector<ll>> vct = (pow_mod(v, p / 2));
		return multiply(vct);
	}
}

int main() {
	int k, n;
	cin >> k;
	for (int i = 0; i < k; i++)
	{
		cin >> n;
		if (n % 3)
		{
			cout << 0 << endl;
		}
		else
		{
			n /= 3;
			int p = 2;
			ll a1 = 1, a2 = 1;
			while (n > 0)
			{
				if (n & 1)
				{
					vector<vector<ll>> a = { {4,-1},{1,0} };
					a = pow_mod(a, p / 2);
					ll tmp1 = a1;
					ll tmp2 = a2;
					a1 = (tmp1 * a[0][0]) % MOD + (tmp2 * ((a[0][1] + MOD) % MOD)) % MOD;
					a2 = (tmp1 * a[1][0]) % MOD + (tmp2 * ((a[1][1] + MOD) % MOD)) % MOD;
				}
				p *= 2;
				n >>= 1;
			}
			cout << a1 % MOD << endl;
		}
	}
	return 0;
}