#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
long long dp[3][3],temp[3][3];
int main()
{
int t;
scanf("%d",&t);
while (t --) {
int n,i,j,k,cur;
long long ans;
scanf("%d",&n);
if (n == 1) {
ans = 3;
printf("%lld\n",ans);
continue;
}
for (i = 0; i < 3; i++) {
for (j = 0; j < 3; j++) {
dp[i][j] = 1;
}
}
for (i = 3; i <= n; i++) {
for (j = 0; j < 3; j++) {
for (k = 0; k < 3; k++) {
temp[j][k] = 0;
}
}
for (j = 0; j < 3; j++) {
for (k = 0; k < 3; k++) {
for (cur = 0; cur < 3; cur++) {
temp[k][cur] = (temp[k][cur] + dp[j][k]) % MOD;
}
}
}
temp[1][2] = (temp[1][2] - dp[0][1] + MOD) % MOD;
for (j = 0; j < 3; j++) {
for (k = 0; k < 3; k++) {
dp[j][k] = temp[j][k];
}
}
}
ans = 0;
for (i = 0; i < 3; i++) {
for (j = 0; j < 3; j++) {
ans = (ans + dp[i][j]) % MOD;
}
}
printf("%lld\n",ans);
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CgojZGVmaW5lIE1PRCAxMDAwMDAwMDA3Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKbG9uZyBsb25nIGRwWzNdWzNdLHRlbXBbM11bM107CgppbnQgbWFpbigpCnsKCWludCB0OwoJc2NhbmYoIiVkIiwmdCk7Cgl3aGlsZSAodCAtLSkgewoJCWludCBuLGksaixrLGN1cjsKCQlsb25nIGxvbmcgYW5zOwoJCXNjYW5mKCIlZCIsJm4pOwoJCWlmIChuID09IDEpIHsKCQkJYW5zID0gMzsKCQkJcHJpbnRmKCIlbGxkXG4iLGFucyk7CgkJCWNvbnRpbnVlOwoJCX0KCQlmb3IgKGkgPSAwOyBpIDwgMzsgaSsrKSB7CgkJCWZvciAoaiA9IDA7IGogPCAzOyBqKyspIHsKCQkJCWRwW2ldW2pdID0gMTsKCQkJfQoJCX0KCQlmb3IgKGkgPSAzOyBpIDw9IG47IGkrKykgewoJCQlmb3IgKGogPSAwOyBqIDwgMzsgaisrKSB7CgkJCQlmb3IgKGsgPSAwOyBrIDwgMzsgaysrKSB7CgkJCQkJdGVtcFtqXVtrXSA9IDA7CgkJCQl9CgkJCX0KCQkJZm9yIChqID0gMDsgaiA8IDM7IGorKykgewoJCQkJZm9yIChrID0gMDsgayA8IDM7IGsrKykgewoJCQkJCWZvciAoY3VyID0gMDsgY3VyIDwgMzsgY3VyKyspIHsKCQkJCQkJdGVtcFtrXVtjdXJdID0gKHRlbXBba11bY3VyXSArIGRwW2pdW2tdKSAlIE1PRDsKCQkJCQl9CgkJCQl9CgkJCX0KCQkJdGVtcFsxXVsyXSA9ICh0ZW1wWzFdWzJdIC0gZHBbMF1bMV0gKyBNT0QpICUgTU9EOwoJCQlmb3IgKGogPSAwOyBqIDwgMzsgaisrKSB7CgkJCQlmb3IgKGsgPSAwOyBrIDwgMzsgaysrKSB7CgkJCQkJZHBbal1ba10gPSB0ZW1wW2pdW2tdOwoJCQkJfQoJCQl9CgkJfQoJCWFucyA9IDA7CgkJZm9yIChpID0gMDsgaSA8IDM7IGkrKykgewoJCQlmb3IgKGogPSAwOyBqIDwgMzsgaisrKSB7CgkJCQlhbnMgPSAoYW5zICsgZHBbaV1bal0pICUgTU9EOwoJCQl9CgkJfQoJCXByaW50ZigiJWxsZFxuIixhbnMpOwoJfQoJcmV0dXJuIDA7Cn0=