Rcently, Xiaoxi notice a interesting sequence of number, which can be construct in a function below:

int a[MAXN];
void build() {
   int cnt = 0;
   for (int i = 0; i <= n; i++) {
      a[i] = 2 * (cnt + 1);
      int u = cnt;
      for (int k = 1; k <= a[i]; k++) ++cnt;
      for (int h = 1; h <= u; h++) ++cnt;
   }
}

Of course, some unavoidable arithmetic overflow will occur in the above construction function (that is, beyond the int range). Xiaoxi hopes you can improve the above procedure to avoid any possible arithmetic overflow.

After improvement, Xiao Xi wants to know the results after module 1000000007 (1e9 + 7) with the values of some items in the sequence (a[i]) .

The first line of data is the number of cases T.(T<=50000).

Then T lines, each line contains a number n which means the nth number in above sequence a[] Xiaoxi want to know .

0 <= n <= 1e9

For each query, print an integer respecting your answer in one line.