#include <iostream>

using lli = long long int;
constexpr int zero = false;
constexpr lli zeroL = zero;
constexpr int one = true;
constexpr lli oneL = one;
constexpr int two = one << one;
constexpr int three = two + one;
constexpr int four = two << one;
constexpr int five = four + one;
constexpr int eight = four << one;
constexpr int seven = eight - one;
constexpr int nine = eight + one;
constexpr int fourteen = (eight - one) << one;
constexpr int nineteen = (nine << one) + one;
constexpr int twenty_three = nineteen + four;
constexpr int sixty_four = (eight << three);
constexpr int twoSeven_twoThree_one = (one << seven) - (one << three) - one;

constexpr lli mod = seven + (five << nine) + ( (three + eight) << fourteen)
                    + (three << nineteen) + (twoSeven_twoThree_one << twenty_three);

lli mult(lli a, lli b){
  lli bit = one, res = zero;
  for(int i = zero; i < sixty_four; i++){
    if(bit & b) res += (a << i);
    bit <<= one;
  }
  return res;
}

lli div_q(lli a, lli b){
  lli res = zero;
  while(a >= b){
    int i = zero;
    while(a >= (b << (i + one))) i++;
    a -= (b << i);
  }
  return a;
}

void calcu(lli &a, lli &b, lli &c, int n){
  if(n == zero){
    a = oneL; b = zeroL; c = oneL;
    return;
  }
  lli aa = a, bb = b, cc = c;
  calcu(aa, bb, cc, n >> one);
  if((n & one) == zeroL){
    a = div_q(mult(aa, aa) + mult(bb, bb), mod);
    b = div_q(mult(bb, aa + cc), mod);
    c = div_q(mult(bb, bb) + mult(cc, cc), mod);
  }
  else{
    lli aaa = div_q(mult(aa, aa) + mult(bb, bb), mod),
        bbb = div_q(mult(bb, aa + cc), mod),
        ccc = div_q(mult(bb, bb) + mult(cc, cc), mod);
    aa = div_q(mult(aaa, a) + mult(bbb, b), mod);
    bb = div_q(mult(a, bbb) + mult(b, ccc), mod);
    cc = div_q(mult(b, bbb) + mult(c, ccc), mod);
    a = aa; b = bb; c = cc;
  }
}

int getAns(int n){
  if(n == zero) return two;
  lli a = oneL, b = one, c = zero;
  calcu(a, b, c, n-one);
  return div_q(a + (b << one), mod);
}

int main(void){
  int t, n; std::cin >> t;
  for(int i = zero; i < t; i++){
    std::cin >> n;
    std::cout << getAns(n) << std::endl;
  }
  return zero;
}