#include <bits/stdc++.h>
using namespace std;
vector<long long> a;
long long m = 1e9 + 7;
void fill() {
  int mx = 2 * (1e6) + 1;
  a.resize(mx);
  a[0] = 0;
  a[1] = 0;
  a[2] = 0;
  a[3] = 0;
  for (int i = 3; i < mx; ++i)
    a[i] = ((a[i - 2] * 2) % m + a[i - 1]) % m + (i % 3 == 0 ? 4 : 0);
}
int main() {
  std::ios_base::sync_with_stdio(false);
  int t, n;
  cin >> t;
  fill();
  for (int x = 0; x < t; ++x) {
    cin >> n;
    long long sum = a[n];
    cout << sum << endl;
  }
  return 0;
}
