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;
const int P = 1000000007;
inline void add(int &a, int b) {
  a += b;
  if (a >= P) a -= P;
}
inline void sub(int &a, int b) {
  a -= b;
  if (a < 0) a += P;
}
namespace fio {
char buf[(1 << 21)], wbuf[(1 << 21)];
int idx, nidx, widx, cnt[2000003];
static inline int readChar() {
  if (idx == nidx) {
    nidx = fread(buf, sizeof(char), (1 << 21), stdin);
    if (nidx == 0) return 0;
    idx = 0;
  }
  return buf[idx++];
}
static inline int readInt() {
  int sum = 0;
  char now = readChar();
  bool flag = false;
  while (now == ' ' && now == '\n') now = readChar();
  if (now == '-') {
    flag = true;
    now = readChar();
  }
  while (now != ' ' && now != '\n' && now != '\0') {
    sum = 10 * sum + now - '0';
    now = readChar();
  }
  return (flag) ? -sum : sum;
}
static inline long long readLong() {
  long long sum = 0;
  char now = readChar();
  bool flag = false;
  while (now == ' ' && now == '\n') now = readChar();
  if (now == '-') {
    flag = true;
    now = readChar();
  }
  while (now != ' ' && now != '\n' && now != '\0') {
    sum = 10 * sum + now - '0';
    now = readChar();
  }
  return (flag) ? -sum : sum;
}
static inline int uintSize(int n) {
  int isz = 1;
  if (n < 0) n = -n;
  while (n >= 10) {
    isz++;
    n /= 10;
  }
  return isz;
}
static inline void flush() {
  fwrite(wbuf, sizeof(char), widx, stdout);
  widx = 0;
}
static inline void writeInt(int n) {
  int isz = uintSize(n);
  if (n < 0) {
    n = -n;
    wbuf[widx++] = '-';
  }
  if (widx + isz >= (1 << 21)) {
    flush();
  }
  int next = widx + isz;
  while (isz--) {
    wbuf[widx + isz] = n % 10 + '0';
    n /= 10;
  }
  widx = next;
}
static inline void newLine() {
  if (idx == (1 << 21)) {
    flush();
  }
  wbuf[widx++] = '\n';
}
};  // namespace fio
int dp[66][16], s[66][16];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int t = fio::readInt();
  for (int j = 0; j < 14; j++) {
    dp[0][j] = j < 8;
  }
  while (t--) {
    long long m = fio::readLong();
    int k = 63 - __builtin_clzll(m);
    for (int j = m & 1; j < 14; j += 2) {
      s[0][(j >> 1) + 1] = s[0][j >> 1];
      add(s[0][(j >> 1) + 1], dp[0][j]);
    }
    for (int i = 1; i <= k; i++) {
      int d = m >> i & 1;
      int c = i ? (13 - (m >> (i - 1) & 1)) >> 1 : 0;
      for (int j = d; j < 14; j += 2) {
        dp[i][j] = s[i - 1][(j < c ? j : c) + 1];
        sub(dp[i][j], s[i - 1][j >= 7 ? j - 7 : 0]);
        s[i][(j >> 1) + 1] = s[i][j >> 1];
        add(s[i][(j >> 1) + 1], dp[i][j]);
      }
    }
    fio::writeInt(dp[k][(m >> k & 1)]);
    fio::newLine();
  }
  fio::flush();
  return 0;
}
