The Bubble Cup hypothesis stood unsolved for 130 years. Who ever proves the hypothesis will be regarded as one of the greatest mathematicians of our time! A famous mathematician Jerry Mao managed to reduce the hypothesis to this problem:

Given a number m, how many polynomials P with coefficients in set {\{0,1,2,3,4,5,6,7\}} have: P(2)=m?

Help Jerry Mao solve the long standing problem!

Input

The first line contains a single integer t (1 ≤ t ≤ 5⋅ 10^5) - number of test cases.

On next line there are t numbers, m_i (1 ≤ m_i ≤ 10^{18}) - meaning that in case i you should solve for number m_i.

Output

For each test case i, print the answer on separate lines: number of polynomials P as described in statement such that P(2)=m_i, modulo 10^9 + 7.

Example

Input


2
2 4


Output


2
4

Note

In first case, for m=2, polynomials that satisfy the constraint are x and 2.

In second case, for m=4, polynomials that satisfy the constraint are x^2, x + 2, 2x and 4.
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse3", "sse2", "sse")
#pragma GCC optimize("inline", "fast-math", "unroll-loops", \
                     "no-stack-protector")
using namespace std;
const int MAXN = 1e6 + 10;
const int MM = 1e9 + 7;
int a[555];
const int L = 7;
int f[111][111];
void upd(int &x, int y) {
  x += y;
  if (x >= MM) x -= MM;
}
const int NICO = 16;
const int UMI = 4;
long long gg[8][8][1 << (NICO / 2)];
int g[8][8][1 << NICO];
int n;
void gao(long long m, int _) {
  n = 0;
  while (n < NICO / 2) {
    n++;
    a[n] = m % 2;
    m = m / 2;
  }
  for (int i = 0; i <= n; i++)
    for (int j = 0; j <= L; j++) f[i][j] = 0;
  f[0][_] = 1;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j <= L; j++) {
      if (f[i][j]) {
        int o = (j ^ a[i + 1]) & 1;
        for (int k = o; k < 8; k += 2) {
          upd(f[i + 1][(j + k) >> 1], f[i][j]);
        }
      }
    }
  }
}
void prework() {
  for (int _ = 0; _ <= L; _++) {
    for (int m = 0; m < (1 << (NICO / 2)); m++) {
      gao(m, _);
      for (int i = 0; i <= L; i++) {
        gg[_][i][m] = f[n][i];
      }
    }
  }
  int kke = NICO / 2;
  int umi = 1 << (NICO / 2);
  umi -= 1;
  for (int m = 0; m < (1 << NICO); m++) {
    for (int i = 0; i <= L; i++)
      for (int k = 0; k <= L; k++) {
        long long tmp = 0;
        for (int j = 0; j <= L; j++) {
          tmp += (gg[i][j][m & umi] * gg[j][k][m >> kke]);
        }
        g[i][k][m] = tmp % MM;
      }
  }
}
long long h[10][111];
inline void upd2(long long &x, long long y) { x = (x + y) % MM; }
void solve(int casi) {
  long long m;
  scanf("%lld", &m);
  if (m % 8 == 0 || m % 8 == 1) {
    long long u = m / 8 * 2 + 1;
    u %= MM;
    u = u * u % MM;
    printf("%lld\n", u);
    return;
  } else if (m % 8 == 2 || m % 8 == 3) {
    long long u = m / 8 * 2 + 1;
    u %= MM;
    u = u * (u + 1) % MM;
    printf("%lld\n", u);
    return;
  } else if (m % 8 == 4 || m % 8 == 5) {
    long long u = m / 8 * 2 + 1;
    u %= MM;
    u = (u + 1) * (u + 1) % MM;
    printf("%lld\n", u);
    return;
  } else if (m % 8 == 6 || m % 8 == 7) {
    long long u = m / 8 * 2 + 1;
    u %= MM;
    u = (u + 1) * (u + 2) % MM;
    printf("%lld\n", u);
    return;
  }
  for (int u = 0; u <= UMI; u++)
    for (int i = 0; i <= L; i++) h[u][i] = 0;
  h[0][0] = 1;
  int MAKI = (1 << NICO) - 1;
  int u = 0;
  for (u = 0; u < UMI; u++) {
    for (int i = 0; i <= L; i++)
      if (h[u][i])
        for (int j = 0; j <= L; j++) {
          upd2(h[u + 1][j], h[u][i] * g[i][j][m & MAKI]);
        }
    m >>= NICO;
    if (m == 0) break;
  }
  printf("%lld\n", h[min(UMI, u + 1)][0]);
}
int main() {
  prework();
  int T = 1;
  scanf("%d", &T);
  for (int i = 1; i <= T; i++) solve(i);
  return 0;
}
