#include <bits/stdc++.h>
using namespace std;
const int32_t INFint = 1e9;
const long long INFll = 1e18;
const long long INF = 9e18;
const long double PI = acos(-1);
long long powersOfTwo[31] = {
    1,         2,         4,         8,        16,       32,       64,
    128,       256,       512,       1024,     2048,     4096,     8192,
    16384,     32768,     65536,     131072,   262144,   524288,   1048576,
    2097152,   4194304,   8388608,   16777216, 33554432, 67108864, 134217728,
    268435456, 536870912, 1073741824};
long long power(long long x, long long y) {
  long long r = 1;
  while (y > 0) {
    if (y & 1) r = r * x;
    y = y >> 1;
    x = x * x;
  }
  return r;
}
long long powerMod(long long x, long long y, long long p) {
  long long res = 1;
  x %= p;
  while (y > 0) {
    if (y & 1) res = (res * x) % p;
    y = y >> 1;
    x = (x * x) % p;
  }
  return res;
}
long long gcd(long long a, long long b) {
  if (!b) return a;
  return gcd(b, a % b);
}
long long lcm(long long a, long long b) { return (a * b) / gcd(a, b); }
vector<vector<long long> > dp(2000005, vector<long long>(2));
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  for (long long i = 3; i < 2000005; i++) {
    dp[i][1] = 4 + dp[i - 1][0] + dp[i - 2][0] + dp[i - 2][0];
    dp[i][0] = max({dp[i - 1][1] + dp[i - 2][1] + dp[i - 2][1],
                    dp[i - 1][1] + dp[i - 2][0] + dp[i - 2][0],
                    dp[i - 1][0] + dp[i - 2][1] + dp[i - 2][1]});
    dp[i][1] %= 1000000007;
    dp[i][0] %= 1000000007;
  }
  long long tt = 1;
  cin >> tt;
  while (tt--) {
    long long n;
    cin >> n;
    cout << max(dp[n][0], dp[n][1]) << '\n';
  }
  cerr << "Time : " << 1000 * (long double)clock() / (long double)CLOCKS_PER_SEC
       << "ms\n";
  ;
}
