#include <bits/stdc++.h>
using namespace std;

static const uint32_t MOD = 1000000007u;
static const int N = 100;

// Матрица с обычным и транспонированным представлением
struct Matrix {
    alignas(64) uint32_t a[N][N];
    alignas(64) uint32_t at[N][N];

    Matrix(bool zero = true) {
        if (zero) {
            memset(a, 0, sizeof(a));
            memset(at, 0, sizeof(at));
        }
    }
    static Matrix identity() {
        Matrix R;
        for (int i = 0; i < N; ++i) {
            R.a[i][i] = 1;
            R.at[i][i] = 1;
        }
        return R;
    }
};

// Быстрое умножение с блокированием и prefetch.
// Параметры подобраны для N=100 и задач с малыми значениями элементов.
inline Matrix mul_opt(const Matrix &A, const Matrix &B) {
    Matrix R;
    const int BS = 16;    // блок по i/j
    const int KCH = 20;   // длина k-чанка (большая, чтобы реже редуцировать)

    for (int ii = 0; ii < N; ii += BS) {
        int iimax = std::min(N, ii + BS);
        for (int jj = 0; jj < N; jj += BS) {
            int jjmax = std::min(N, jj + BS);

            for (int kk = 0; kk < N; kk += KCH) {
                int kkmax = std::min(N, kk + KCH);

                for (int i = ii; i < iimax; ++i) {
                    const uint32_t * __restrict__ Ai = A.a[i];
                    uint32_t * __restrict__ Ri = R.a[i];

                    for (int j = jj; j < jjmax; ++j) {
                        // Вытаскиваем B^T строку j
                        const uint32_t * __restrict__ Btj = B.at[j];

                        // Намеренная предзагрузка кусочка Btj для следующей итерации
                        __builtin_prefetch(Btj + kk, 0, 1);

                        uint64_t sum = (uint64_t)Ri[j];

                        // Развёрнутый цикл по k (обычно kkmax - kk == KCH == 20)
                        int k = kk;

                        // развёртка по 4
                        for (; k + 3 < kkmax; k += 4) {
                            sum += (uint64_t)Ai[k]     * (uint64_t)Btj[k];
                            sum += (uint64_t)Ai[k + 1] * (uint64_t)Btj[k + 1];
                            sum += (uint64_t)Ai[k + 2] * (uint64_t)Btj[k + 2];
                            sum += (uint64_t)Ai[k + 3] * (uint64_t)Btj[k + 3];
                        }
                        // остаток
                        for (; k < kkmax; ++k) {
                            sum += (uint64_t)Ai[k] * (uint64_t)Btj[k];
                        }

                        // редукция только когда надо (редко)
                        if (sum >= (1ULL << 61)) sum %= MOD;
                        Ri[j] = (uint32_t)(sum % MOD);
                    }
                }
            }

            // Обновление транспонированной версии R.at для блока (ii..iimax) x (jj..jjmax)
            for (int i = ii; i < iimax; ++i) {
                uint32_t * __restrict__ Ri = R.a[i];
                for (int j = jj; j < jjmax; ++j) {
                    R.at[j][i] = Ri[j];
                }
            }
        }
    }
    return R;
}

Matrix power_fast(long long e, const vector<Matrix> &precalc) {
    Matrix res = Matrix::identity();
    int pos = 0;
    while (e) {
        if (e & 1) res = mul_opt(res, precalc[pos]);
        ++pos;
        e >>= 1;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    if (!(cin >> t)) return 0;

    vector<long long> ns;
    ns.reserve(t);
    long long max_n = 0;
    for (int i = 0; i < t; ++i) {
        long long n;
        cin >> n;
        ns.push_back(n);
        if (n > max_n) max_n = n;
    }

    // предвычислим gcd таблицу 0..9
    int G[10][10];
    for (int i = 0; i < 10; ++i)
        for (int j = 0; j < 10; ++j)
            G[i][j] = std::gcd(i, j);

    Matrix base, mul;
    for (int i = 0; i < 10; ++i)
        for (int j = 0; j < 10; ++j)
            for (int k = 0; k < 10; ++k) {
                uint32_t val = (G[i][j] != G[j][k]) ? 1u : 0u;
                // Сохраняем поведение оригинала (в одном из ранних вариантов base задавался только при i!=0)
                if (i != 0) base.a[i * 10 + j][j * 10 + k] = val;
                mul.a[i * 10 + j][j * 10 + k] = val;
            }

    // заполним транспонированные версии единожды
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j) {
            base.at[j][i] = base.a[i][j];
            mul.at[j][i]  = mul.a[i][j];
        }

    // определим максимально нужный бит для (n-3)
    long long maxExp = 0;
    for (long long n : ns) if (n >= 3) maxExp = max(maxExp, n - 3);

    int maxBit = 0;
    if (maxExp > 0) maxBit = 63 - __builtin_clzll((unsigned long long)maxExp);

    // прекалькуляция степеней (только до maxBit)
    vector<Matrix> precalc;
    if (maxExp > 0) {
        precalc.reserve(maxBit + 1);
        precalc.push_back(mul);
        for (int i = 1; i <= maxBit; ++i) {
            precalc.push_back(mul_opt(precalc[i - 1], precalc[i - 1]));
        }
    }

    // обработка запросов
    for (long long n : ns) {
        if (n == 2) {
            cout << 90 << endl;
            continue;
        }
        long long e = n - 3;
        Matrix pw = power_fast(e, precalc);
        Matrix res = mul_opt(base, pw);

        uint64_t ans = 0;
        for (int i = 0; i < N; ++i) {
            const uint32_t * __restrict__ Ri = res.a[i];
            for (int j = 0; j < N; ++j) {
                ans += Ri[j];
                if (ans >= (1ULL << 61)) ans %= MOD;
            }
        }
        cout << (ans % MOD) << '\n';
    }

    return 0;
}
