#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using i64 = unsigned long long;
using ld = long double;
template <typename T>
inline T Min(T a, T b, T c) {
  return min(a, min(b, c));
}
template <typename T>
inline T Min(T a, T b, T c, T d) {
  return min(a, min(b, min(c, d)));
}
template <typename T>
inline T Ceil(T a, T b) {
  return ((a % b == 0) ? (a / b) : (a / b + 1));
}
template <typename T>
inline T Floor(T a, T b) {
  return a / b;
}
template <typename T>
inline T Power(T a, T p) {
  T res = 1, x = a;
  while (p) {
    if (p & 1) res = (res * x);
    x = (x * x);
    p >>= 1;
  }
  return res;
}
template <typename T>
inline T gcd(T a, T b) {
  a = abs(a);
  b = abs(b);
  while (b) {
    a = a % b;
    swap(a, b);
  }
  return a;
}
template <typename T>
inline T lcm(T x, T y) {
  return (((x) / gcd((x), (y))) * (y));
}
template <typename T1, typename T2, typename T3>
struct Pair {
  T1 first;
  T2 second;
  T3 third;
};
template <typename T1, typename T2, typename T3, typename T4>
struct Pair4 {
  T1 first;
  T2 second;
  T3 third;
  T4 fourth;
};
using ii = pair<int, int>;
using iii = Pair<int, int, int>;
using iiii = Pair4<int, int, int, int>;
const double EPS = 1e-7;
const double PI = acos(-1.0);
const ll LLINF = (ll)1e18 + 1;
const int INF = (int)1e9 + 1;
const int MOD = (int)1e9 + 7;
const int N = (int)2e6 + 10;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  vector<int> dp(N + 10);
  dp[3] = 4, dp[4] = 4;
  for (int i = 5; i <= N; ++i) {
    dp[i] = ((dp[i - 1] % MOD) + (2 * dp[i - 2] % MOD)) % MOD;
    if (i % 3 == 0) {
      dp[i] += 4;
      dp[i] %= MOD;
    }
  }
  int tc;
  cin >> tc;
  while (tc--) {
    function<void(void)> Solve = [&]() {
      int n;
      cin >> n;
      if (n < 3) {
        cout << "0\n";
      } else {
        cout << dp[n] << '\n';
      }
    };
    Solve();
  }
  return 0;
}
