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>
using namespace std;
const int next_x[8] = {0, 1, -1, 0, 1, 1, -1, -1};
const int next_y[8] = {1, 0, 0, -1, 1, -1, -1, 1};
const int inf = 1e9 + 5;
const long long linf = 1e18 + 5;
const double PI = acos(-1.0);
const double eps = 1e-8;
const int MAXN = 70 + 5;
const int M = MAXN * 20 + 10;
const int N = 4e7 + 1e6;
const int fix = 500 * 500 + 5;
struct IO {
  char buf[(1 << 20)], *p1, *p2;
  char pbuf[(1 << 20)], *pp;
  IO() : p1(buf), p2(buf), pp(pbuf) {}
  ~IO() { fwrite(pbuf, 1, pp - pbuf, stdout); }
  inline char gc() {
    if (p1 == p2) p2 = (p1 = buf) + fread(buf, 1, (1 << 20), stdin);
    return p1 == p2 ? ' ' : *p1++;
  }
  inline bool blank(char ch) {
    return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';
  }
  template <class T>
  inline void read(T &x) {
    register double tmp = 1;
    register bool sign = 0;
    x = 0;
    register char ch = gc();
    for (; !(ch >= '0' && ch <= '9'); ch = gc())
      if (ch == '-') sign = 1;
    for (; (ch >= '0' && ch <= '9'); ch = gc()) x = x * 10 + (ch - '0');
    if (ch == '.')
      for (ch = gc(); (ch >= '0' && ch <= '9'); ch = gc())
        tmp /= 10.0, x += tmp * (ch - '0');
    if (sign) x = -x;
  }
  inline void read(char *s) {
    register char ch = gc();
    for (; blank(ch); ch = gc())
      ;
    for (; !blank(ch); ch = gc()) *s++ = ch;
    *s = 0;
  }
  inline void read(char &c) {
    for (c = gc(); blank(c); c = gc())
      ;
  }
  inline void push(const char &c) {
    if (pp - pbuf == (1 << 20)) fwrite(pbuf, 1, (1 << 20), stdout), pp = pbuf;
    *pp++ = c;
  }
  template <class T>
  inline void write(T x) {
    if (x < 0) x = -x, push('-');
    static T sta[35];
    T top = 0;
    do {
      sta[top++] = x % 10, x /= 10;
    } while (x);
    while (top) push(sta[--top] + '0');
  }
  template <class T>
  inline void write(T x, char lastChar) {
    write(x), push(lastChar);
  }
} io;
const int MOD = 1e9 + 7;
int n;
int d[MAXN];
int f[MAXN][15];
bool v[MAXN][15];
unordered_map<long long, int> ans;
int solve(int len, int c) {
  if (len == d[0] + 1) return c == 0;
  if (v[len][c]) return f[len][c];
  v[len][c] = 1, f[len][c] = 0;
  int &ans = f[len][c];
  for (register int i = (0), I = (7) + 1; i < I; ++i) {
    int _c = (i + c), t = (_c & 1);
    if (t == d[len]) {
      ans += solve(len + 1, _c / 2);
      if (ans >= MOD) ans -= MOD;
    }
  }
  return ans;
}
inline __int128 read() {
  __int128 sum = 0;
  char ch = getchar();
  while (!(ch >= '0' && ch <= '9')) ch = getchar();
  while (ch >= '0' && ch <= '9') sum = sum * 10 + ch - 48, ch = getchar();
  return sum;
}
inline void out(__int128 x) {
  if (x > 9) out(x / 10);
  putchar(x % 10 + '0');
}
int work() {
  int _CASE;
  scanf("%d", &_CASE);
  for (register int case_num = (1), I = (_CASE) + 1; case_num < I; ++case_num) {
    __int128 n = read();
    int f = (n & 1) ? -1 : 1;
    long long ans = ((n + 1) * (f + n + 6) + 9) / 16 % MOD;
    printf("%lld\n", ans);
  }
  return 0;
}
int main() {
  work();
  return 0;
}
