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 optimize("unroll-loops")
using namespace std;
template <typename U, typename V>
void Min(U &a, const V &b) {
  if (a > b) a = b;
}
template <typename U, typename V>
void Max(U &a, const V &b) {
  if (a < b) a = b;
}
template <typename U, typename V>
void add(U &a, const V &b) {
  a = (a + b) % 1000000007;
}
template <typename U>
U gcd(U a, U b) {
  if (a == 0) return b;
  if (b == 0) return a;
  if (a >= b)
    return gcd(a % b, b);
  else
    return gcd(a, b % a);
}
int pow(int a, int b) {
  int ans = 1;
  while (b) {
    if (b & 1) ans = 1LL * ans * a % 1000000007;
    a = 1LL * a * a % 1000000007;
    b >>= 1;
  }
  return ans;
}
int pow(int a, long long b, int c) {
  int ans = 1;
  while (b) {
    if (b & 1) ans = 1LL * ans * a % c;
    a = 1LL * a * a % c;
    b >>= 1;
  }
  return ans;
}
long long Read() {
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    ch = getchar();
  }
  long long v = 0;
  while ('0' <= ch && ch <= '9') {
    v = v * 10 + (int)(ch - '0');
    ch = getchar();
  }
  return v;
}
void Write(int first) {
  int len = 0;
  static int d[100];
  while (first > 0) {
    d[len++] = first % 10;
    first /= 10;
  }
  for (int i = len - 1; i >= 0; i--) {
    putchar('0' + d[i]);
  }
  if (len == 0) {
    putchar('0');
  }
  putchar('\n');
}
int dp[7], b[65], s[8];
int main() {
  int ca = 0, T, i, j, k, K, m;
  long long n;
  scanf("%d", &T);
  while (T--) {
    n = Read();
    m = 0;
    while (n) b[m++] = n & 1, n >>= 1;
    for (int i = 1; i < 8; i++) s[i] = 1;
    for (int i = m - 1; i >= 0; i--) {
      if (b[i] == 0) {
        dp[0] = s[4] - s[0];
        dp[1] = dp[2] = s[5] - s[1];
        dp[3] = dp[4] = s[6] - s[2];
        dp[5] = dp[6] = s[7] - s[3];
      } else {
        dp[0] = dp[1] = s[4] - s[0];
        dp[2] = dp[3] = s[5] - s[1];
        dp[4] = dp[5] = s[6] - s[2];
        dp[6] = s[7] - s[3];
      }
      for (int j = 0; j < 7; j++) {
        if (dp[j] < 0) dp[j] += 1000000007;
        s[j + 1] = s[j] + dp[j];
        if (s[j + 1] >= 1000000007) s[j + 1] -= 1000000007;
      }
    }
    Write(dp[0]);
  }
}
