#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;
const ll mod=10007;
const int N=3;
int n;
struct matrix {
	ll num[10][10];
	
	matrix() { memset(num, 0, sizeof(num)); }
	
	matrix operator*(const matrix &x) {
		matrix c;
		for (int i = 1; i <= N; ++i)
			for (int j = 1; j <= N; ++j)
				for (int k = 1; k <= N; ++k)
					c.num[i][j] = (c.num[i][j] + num[i][k] * x.num[k][j]) % mod;
		return c;
	}
	
	matrix &operator=(const matrix &x) {
		for (int i = 1; i <= N; ++i)
			for (int j = 1; j <= N; ++j)
				num[i][j] = x.num[i][j];
		return *this;
	}
};
int table[4][4]={{0,0,0,0},{0,2,0,1},{0,0,2,1},{0,2,2,2}};
matrix pow_mod(matrix& x,int k) {
	matrix ans;
	for (int i = 1; i <= N; ++i)ans.num[i][i] = 1;
	while (k) {
		if (k & 1)ans = ans * x;
		x = x * x;
		k >>= 1;
	}
	return ans;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int _;
	cin >> _;
	while (_--) {
		cin >> n;
		matrix ans;
		for (int i = 1; i <= N; ++i) {
			for (int j = 1; j <= N; ++j)
				ans.num[i][j] = table[i][j];
		}
		ans = pow_mod(ans, n - 1);
		ll tot = (ans.num[2][2] * 2 + ans.num[2][3] * 2) % mod;
		cout << tot << endl;
	}
	return 0;
}

a[i]表示前i块红色与绿色全为奇数的方案数。b[i]表示前i块红色与绿色全为偶数的方案数。c[i]表示前i块红色与绿色的块数一奇一偶的方案数。

因此转移方程可以表示为：

a[i]=2a[i-1]+0b[i-1]+1*c[i-1]

b[i]=0a[i-1]+2b[i-1]+1*c[i-1]

c[i]=2a[i-1]+2b[i-1]+2*c[i-1]

因此矩阵可以构造出，所要求的即为b[n]的值。 ————————————————