#include <bits/stdc++.h>
using namespace std;
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int T, mod = 1e9 + 7;
  vector<long long> a(3000000, 0), b(3000000, 0);
  a[3] = 4;
  b[3] = 1;
  for (int i = 4; i <= 2300000; i++) {
    a[i] = (a[i - 1] + 2 * a[i - 2]) % mod;
    if (b[i] == 0 && b[i - 1] == 0 && b[i - 2] == 0) {
      a[i] += 4;
      b[i] = 1;
    }
  }
  cin >> T;
  while (T--) {
    int n;
    cin >> n;
    cout << a[n] << '\n';
    ;
  }
  return 0;
}
