#include <cstdio>
#include <cstdint>
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <tuple>
#include <functional>

constexpr intmax_t zero = false;
constexpr intmax_t one = true;
constexpr intmax_t two = sizeof(short);

auto add = std::plus<intmax_t>();
auto sub = std::minus<intmax_t>();
auto mul = std::multiplies<intmax_t>();

auto v = [](auto x) { return add(x, one); };
auto w = [](auto x) { return add(x, x); };

intmax_t p = v(w(v(w(v(w(w(w(w(w(w(w(v(w(w(v(w(w(w(v(w(v(w(w(v(w(w(v(w(v(w(w(w(v(w(v(w(v(w(w(v(w(v(w(one))))))))))))))))))))))))))))))))))))))))))));

auto mod = [=](auto x) { return std::modulus<intmax_t>()(x, p); };

using matrix = std::tuple<intmax_t, intmax_t, intmax_t, intmax_t>;

matrix matmul(matrix const& s, matrix const& t) {
  intmax_t a, b, c, d;
  intmax_t e, f, g, h;
  std::tie(a, b, c, d) = s;
  std::tie(e, f, g, h) = t;

  intmax_t i = mod(add(mul(a, e), mul(b, g)));
  intmax_t j = mod(add(mul(a, f), mul(b, h)));
  intmax_t k = mod(add(mul(c, e), mul(d, g)));
  intmax_t l = mod(add(mul(c, f), mul(d, h)));
  return matrix(i, j, k, l);
}

matrix matpow(matrix const& m, intmax_t n) {
  matrix res(one, zero, zero, one);
  for (matrix dbl = m; n; n >>= one) {
    if (n & one) res = matmul(res, dbl);
    dbl = matmul(dbl, dbl);
  }
  return res;
}

int f(int n) {
  n = sub(n, one);
  matrix m(one, one, one, zero);
  intmax_t a, b;
  std::tie(a, b, std::ignore, std::ignore) = matpow(m, n);
  return mod(add(mul(a, one), mul(b, two)));
}

int main() {
  int T;
  std::cin >> T;

  std::vector<int> a(T);
  for (auto& ai: a) {
    std::cin >> ai;
    std::cout << f(ai) << std::endl;
  }
}