#include <bits/stdc++.h>
using namespace std;
mt19937 gen(time(0));
bool IS_ONE_TEST = 0;
long long maxn = 2000005;
vector<long long> c1(maxn), c2(maxn), c3(maxn);
vector<long long> ans(maxn);
void init() {
  long long n;
  n = maxn;
  long long mod = 1e9 + 7;
  c1[1] = 1;
  c1[2] = 1;
  c2[2] = 1;
  for (int i = 3; i <= n; ++i) {
    c3[i] = c2[i - 1];
    c2[i] = c1[i - 1];
    c1[i] = (c3[i] * 2 + c2[i]) % mod;
  }
  for (int i = 0; i <= n; ++i) {
    ans[i] = (c3[i] * 4 + (i >= 3 ? ans[i - 3] : 0)) % mod;
  }
}
void solve() {
  long long n;
  cin >> n;
  cout << ans[n] << endl;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cout << fixed << setprecision(15);
  long long t;
  if (IS_ONE_TEST)
    t = 1;
  else
    cin >> t;
  init();
  while (t-- > 0) {
    solve();
  }
}
