#include<iostream>
#include<vector>
using namespace std;
using LL = long long;
using ULL = unsigned long long;

const LL Zero = {};
LL increment_small(LL x) { auto V = vector<int>(x); V.emplace_back(); return V.size(); }
LL decrement_small(LL x) { auto V = vector<int>(x); V.pop_back(); return V.size(); }
const LL One = increment_small(Zero);
LL power_of_two(LL x) { return One << x; }
const LL BitNum = decrement_small(decrement_small(power_of_two(increment_small(increment_small(power_of_two(power_of_two(One)))))));
LL addition(LL a, LL b) {
    LL crr = Zero, ans = Zero;
    for (LL d = One; d < power_of_two(BitNum); d <<= One) {
        ans |= d & (a ^ b ^ crr);
        crr = d & ((a & b) | (a & crr) | (b & crr));
        crr <<= One;
    }
    return ans;
}
LL subtruction(LL a, LL b) {
    LL crr = Zero, ans = Zero;
    for (LL d = One; d < power_of_two(BitNum); d <<= One) {
        ans |= d & (a ^ b ^ crr);
        crr = d & ((~a & (b | crr)) | (b & crr));
        crr <<= One;
    }
    return ans;
}
LL multiplication(LL a, LL b) {
    LL ans = Zero;
    for (LL d = Zero; d < BitNum; d = addition(d, One)) {
        if (b & power_of_two(d)) ans = addition(ans, a << d);
    }
    return ans;
}
LL power(LL a, LL i) {
    if (i == Zero) return One;
    LL res = power(multiplication(a, a), i >> One);
    if (i & One) res = multiplication(res, a);
    return res;
}

const LL MOD = addition(
    power(
        addition(addition(power_of_two(addition(addition(One, One), One)), One), One),
        addition(power_of_two(addition(addition(One, One), One)), One)
    ),
    subtruction(power_of_two(increment_small(increment_small(One))), One)
);

LL modulo(LL a) {
    for (LL d = subtruction(BitNum >> One, One); d < BitNum; d = subtruction(d, One)) {
        if (a >= MOD << d) a = subtruction(a, MOD << d);
    }
    return a;
}

const LL matrix_dim = power_of_two(One);

struct Matrix {
    LL a = Zero, b = Zero, c = Zero, d = Zero;
};

Matrix multiplication(Matrix l, Matrix r) {
    Matrix res;
    res.a = modulo(addition(multiplication(l.a, r.a), multiplication(l.b, r.c)));
    res.b = modulo(addition(multiplication(l.a, r.b), multiplication(l.b, r.d)));
    res.c = modulo(addition(multiplication(l.c, r.a), multiplication(l.d, r.c)));
    res.d = modulo(addition(multiplication(l.c, r.b), multiplication(l.d, r.d)));
    return res;
}
Matrix power(Matrix a, LL i) {
    if (i == Zero) return { One, Zero, Zero, One };
    Matrix res = power(a, i >> One);
    res = multiplication(res, res);
    if (i & One) res = multiplication(res, a);
    return res;
}

Matrix G = { One, One, One, Zero };

void loop() {
    LL N; cin >> N;
    Matrix powG = power(G, N);
    LL ans = modulo(addition(powG.d << One, powG.b));
    cout << ans << endl;
}

int main() {
    int t; cin >> t;
    for (int i = Zero; i < t; i = addition(i, One)) loop();
    return Zero;
}