#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9 + 7;
const long long LINF = 1e18;
const int INF = 0x3f3f3f3f;
const int MAXN = 2000050;
long long ans[MAXN];
void init() {
  for (int i = 3; i <= MAXN; i++) {
    ans[i] = ans[i - 1] + 2 * ans[i - 2];
    if (i % 3 == 0) ans[i] += 4;
    ans[i] %= MOD;
  }
}
void solve(int T) {
  int n;
  scanf("%d", &n);
  printf("%lld\n", ans[n]);
}
signed main() {
  int t = 1;
  init();
  scanf("%d", &t);
  for (int i = 1; i <= t; i++) {
    solve(i);
  }
}
