#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7, N = 2e6 + 9;
long long f[N];
int32_t main() {
  ios::sync_with_stdio(0), cin.tie(0);
  f[3] = f[4] = 4;
  for (long long i = 5; i < N; i++) {
    f[i] = (f[i - 1] + 2 * f[i - 2] % mod) % mod;
    if (i % 3 == 0) f[i] = (f[i] + 4) % mod;
  }
  long long T;
  cin >> T;
  while (T--) {
    long long n;
    cin >> n;
    cout << f[n] << "\n";
  }
}
