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

using ll = long long;
const int MOD = 1000000007;

// Максимальное количество состояний (фактически 33, но возьмём с запасом)
const int MAXS = 40;
// Максимальное количество бит для n <= 1e18 (n-2 тоже)
const int LOG = 61;

int S;                                         // реальное число состояний
int gcdtab[10][10];
int idx_state[10][10];                         // idx_state[d][g] -> номер состояния
pair<int,int> states[MAXS];                    // (d, g)

// Матрицы M^(2^k): mpow[k][i][j]
int mpow[LOG][MAXS][MAXS];

// Умножение матриц A*B -> C (размер SxS, всё по модулю MOD)
void matMul(int A[MAXS][MAXS], int B[MAXS][MAXS], int C[MAXS][MAXS]) {
    static int tmp[MAXS][MAXS];
    // локальная копия в tmp, чтобы не портить A/B при C=A/B
    for (int i = 0; i < S; ++i) {
        for (int j = 0; j < S; ++j) {
            tmp[i][j] = 0;
        }
    }
    for (int i = 0; i < S; ++i) {
        for (int k = 0; k < S; ++k) {
            int aik = A[i][k];
            if (!aik) continue;
            ll vk = aik;
            for (int j = 0; j < S; ++j) {
                int bkj = B[k][j];
                if (!bkj) continue;
                ll val = vk * bkj;
                int add = (int)(val % MOD);
                int cur = tmp[i][j] + add;
                if (cur >= MOD) cur -= MOD;
                tmp[i][j] = cur;
            }
        }
    }
    for (int i = 0; i < S; ++i)
        for (int j = 0; j < S; ++j)
            C[i][j] = tmp[i][j];
}

// Умножение вектора v (1xS) на матрицу A (SxS) -> res (1xS)
void vecMul(int v[MAXS], int A[MAXS][MAXS], int res[MAXS]) {
    for (int j = 0; j < S; ++j) res[j] = 0;
    for (int i = 0; i < S; ++i) {
        int vi = v[i];
        if (!vi) continue;
        ll vv = vi;
        for (int j = 0; j < S; ++j) {
            int aij = A[i][j];
            if (!aij) continue;
            ll val = vv * aij;
            int add = (int)(val % MOD);
            int cur = res[j] + add;
            if (cur >= MOD) cur -= MOD;
            res[j] = cur;
        }
    }
}

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

    // gcd для цифр 0..9
    for (int i = 0; i < 10; ++i)
        for (int j = 0; j < 10; ++j)
            gcdtab[i][j] = std::gcd(i, j);

    // Заполняем индекс состояний (d, g)
    for (int i = 0; i < 10; ++i)
        for (int j = 0; j < 10; ++j)
            idx_state[i][j] = -1;

    S = 0;
    for (int a_prev = 0; a_prev < 10; ++a_prev) {
        for (int a_cur = 0; a_cur < 10; ++a_cur) {
            int g = gcdtab[a_prev][a_cur];
            if (idx_state[a_cur][g] == -1) {
                idx_state[a_cur][g] = S;
                states[S] = {a_cur, g};
                ++S;
            }
        }
    }

    // Строим базовую матрицу переходов M = mpow[0]
    for (int i = 0; i < S; ++i)
        for (int j = 0; j < S; ++j)
            mpow[0][i][j] = 0;

    for (int si = 0; si < S; ++si) {
        int d = states[si].first;
        int g = states[si].second;
        for (int x = 0; x < 10; ++x) {
            int new_g = gcdtab[d][x];
            if (new_g == g) continue;              // условие: gcd не должен повторяться
            int sj = idx_state[x][new_g];
            // состояние должно существовать
            mpow[0][si][sj] += 1;
            if (mpow[0][si][sj] >= MOD) mpow[0][si][sj] -= MOD;
        }
    }

    // Предподсчитываем mpow[k] = M^(2^k)
    for (int k = 1; k < LOG; ++k) {
        matMul(mpow[k-1], mpow[k-1], mpow[k]);
    }

    // Начальный вектор v0 для длины 2
    int v0[MAXS];
    for (int i = 0; i < S; ++i) v0[i] = 0;

    for (int a1 = 1; a1 <= 9; ++a1) {
        for (int a2 = 0; a2 <= 9; ++a2) {
            int g = gcdtab[a1][a2];
            int s = idx_state[a2][g];
            v0[s] += 1;
            if (v0[s] >= MOD) v0[s] -= MOD;
        }
    }

    int T;
    cin >> T;
    while (T--) {
        long long n;
        cin >> n;

        if (n == 1) {
            // одноразрядное число: любая цифра 1..9
            cout << 9 << '\n';
            continue;
        }
        if (n == 2) {
            // любые пары (a1,a2): 9*10
            cout << 90 << '\n';
            continue;
        }

        long long e = n - 2;

        int v[MAXS], tmp[MAXS];
        // v = v0
        for (int i = 0; i < S; ++i) v[i] = v0[i];

        int bit = 0;
        while (e > 0) {
            if (e & 1LL) {
                vecMul(v, mpow[bit], tmp);
                for (int i = 0; i < S; ++i) v[i] = tmp[i];
            }
            e >>= 1;
            ++bit;
        }

        int ans = 0;
        for (int i = 0; i < S; ++i) {
            ans += v[i];
            if (ans >= MOD) ans -= MOD;
        }
        cout << ans << '\n';
    }

    return 0;
}
