#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9 + 7;
const int MAXN = 2e6 + 5;
long long dp[MAXN];
int t;
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  dp[1] = (long long)0, dp[2] = (long long)0, dp[3] = (long long)4,
  dp[4] = (long long)4, dp[5] = (long long)12;
  for (int i = 6; i <= MAXN - 2; i++) {
    if (i % 3 == 0)
      dp[i] = (4 + ((((4 * dp[i - 4]) % MOD) + ((4 * dp[i - 3]) % MOD)) % MOD) +
               dp[i - 2]) %
              MOD;
    else
      dp[i] = (((2 * dp[i - 2]) % MOD) + dp[i - 1]) % MOD;
  }
  cin >> t;
  while (t) {
    t--;
    int n;
    cin >> n;
    cerr << "ANS" << endl;
    cout << dp[n] % MOD << endl;
  }
  return 0;
}
