#include <iostream>
#include <array>
using namespace std;
using ll = long long;
constexpr ll zero = static_cast<ll>(NULL);
constexpr ll one = sizeof(char);
constexpr ll two = sizeof(short);
constexpr ll four = sizeof(int);
constexpr ll eight = sizeof(long);
ll MOD;
inline ll add(ll a, ll b)
{
    while (b != zero) {
        ll c = (a & b) << one;
        a ^= b;
        b = c;
    }
    return a;
}
inline ll sub(const ll a, const ll b)
{
    return add(a, add(~b, one));
}
inline ll mul(const ll a, const ll b)
{
    ll ans = zero;
    static const ll sixteen = add(eight, eight);
    static const ll thirtytwo = add(sixteen, sixteen);
    static const ll sixtyfour = add(thirtytwo, thirtytwo);
    for (ll i = zero; i < sixtyfour; i = add(i, one)) {
        if (a & (one << i)) {
            ans = add(ans, b << i);
        }
    }
    return ans;
}
inline ll mod(ll n, ll d = MOD)
{
    ll m = one, q = zero;
    while (d <= n) {
        d <<= one;
        m <<= one;
    }
    while (one < m) {
        d >>= one;
        m >>= one;
        if (n >= d) {
            n = sub(n, d);
            q |= m;
        }
    }
    return n;
}

using Mat = array<array<ll, two>, two>;
Mat mul(const Mat& a, const Mat& b)
{
    Mat ans{{{zero, zero}, {zero, zero}}};
    for (ll i = zero; i < two; i = add(i, one)) {
        for (ll j = zero; j < two; j = add(j, one)) {
            for (ll k = zero; k < two; k = add(k, one)) {
                ans[i][j] = mod(add(ans[i][j], mod(mul(a[i][k], b[k][j]))));
            }
        }
    }
    return ans;
}
Mat power(const Mat& m, const ll n)
{
    if (n == zero) {
        return Mat{{{one, zero}, {zero, one}}};
    }
    if (mod(n, two) == one) {
        return mul(power(m, sub(n, one)), m);
    } else {
        const auto pp = power(m, n >> one);
        return mul(pp, pp);
    }
}

int main()
{
    MOD = one;
    const ll ten = add(two, eight);
    for (ll i = zero; i <= eight; i = add(i, one)) { MOD = mul(MOD, ten); }
    MOD = add(MOD, eight);
    MOD = sub(MOD, one);
    ll T;
    cin >> T;
    const Mat mat{{{one, one}, {one, zero}}};
    for (ll i = zero; i < T; i = add(i, one)) {
        ll N;
        cin >> N;
        const auto ans = power(mat, N);
        cout << mod(add(ans[one][zero], mul(two, ans[one][one]))) << endl;
    }
    return zero;
}