#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e6 + 5;
const int mod = 1e9 + 7;
int n, k;
long long a[maxn];
template <class T>
inline void read(T &res) {
  res = 0;
  T f = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    res = res * 10 + c - '0';
    c = getchar();
  }
  res *= f;
}
long long cal(int n) { return a[n]; }
int nn = 4, mm = 12;
long long call(int i) {
  if (i % 3) return (a[i - 1] + 2 * a[i - 2]) % mod;
  return (a[i - 1] + 2 * a[i - 2] + 4) % mod;
}
void init() {
  a[3] = a[4] = nn;
  a[5] = mm;
  for (int i = 6; i <= maxn; ++i) {
    a[i] = call(i);
  }
}
int main() {
  int qwq;
  init();
  read(qwq);
  while (qwq--) {
    read(n);
    long long ans = cal(n);
    printf("%lld\n", ans);
  }
  return 0;
}
