#pragma GCC optimize("O3","unroll-loops","fast-math")
#include <bits/stdc++.h>
#pragma GCC target("avx2","bmi2","lzcnt","popcnt")
using namespace std;

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

const int MAXS = 40;
const int LOG = 61;

int S;

// gcd для цифр
int gcdtab[10][10];

// индекс состояния (d, g)
int idx_state[10][10];
// сами состояния
pair<int,int> states[MAXS];

// mpow[k] = M^(2^k), матрицы SxS
static int mpow[LOG][MAXS][MAXS];

// начальный вектор для n = 2
int v0[MAXS];

// временные буферы для умножений
int tmpMat[MAXS][MAXS];
int tmpVec[MAXS];

// умножение матриц: C = A * B
inline void matMul(int A[MAXS][MAXS], int B[MAXS][MAXS], int C[MAXS][MAXS]) {
    // обнуляем temp
    for (int i = 0; i < S; ++i) {
        int *row = tmpMat[i];
        for (int j = 0; j < S; ++j) row[j] = 0;
    }

    for (int i = 0; i < S; ++i) {
        int *rowA = A[i];
        int *rowC = tmpMat[i];
        for (int k = 0; k < S; ++k) {
            int aik = rowA[k];
            if (!aik) continue;
            unsigned long long vk = (unsigned long long)aik;
            int *rowB = B[k];
            for (int j = 0; j < S; ++j) {
                int bkj = rowB[j];
                if (!bkj) continue;
                unsigned long long val = vk * (unsigned long long)bkj;
                int add = (int)(val % MOD);
                int cur = rowC[j] + add;
                if (cur >= MOD) cur -= MOD;
                rowC[j] = cur;
            }
        }
    }

    for (int i = 0; i < S; ++i) {
        int *src = tmpMat[i];
        int *dst = C[i];
        for (int j = 0; j < S; ++j) dst[j] = src[j];
    }
}

// умножение вектора v (1xS) на матрицу A (SxS): res = v * A
inline void vecMul(const 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;
        unsigned long long vv = (unsigned long long)vi;
        int *rowA = A[i];
        for (int j = 0; j < S; ++j) {
            int aij = rowA[j];
            if (!aij) continue;
            unsigned long long val = vv * (unsigned long long)aij;
            int add = (int)(val % MOD);
            int cur = res[j] + add;
            if (cur >= MOD) cur -= MOD;
            res[j] = cur;
        }
    }
}

// считаем ответ для конкретного n (n >= 1)
int solve_n(long long n) {
    if (n == 1) return 9;      // 1..9
    if (n == 2) return 90;     // 9*10

    long long e = n - 2;

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

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

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

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

    // precompute gcd
    for (int i = 0; i < 10; ++i)
        for (int j = 0; j < 10; ++j)
            gcdtab[i][j] = std::gcd(i, j);

    // индексы состояний
    for (int i = 0; i < 10; ++i)
        for (int j = 0; j < 10; ++j)
            idx_state[i][j] = -1;

    // строим множество состояний (d, g = gcd(prev, d))
    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;
            int sj = idx_state[x][new_g];
            int val = mpow[0][si][sj] + 1;
            if (val >= MOD) val -= MOD;
            mpow[0][si][sj] = val;
        }
    }

    // степени матрицы
    for (int k = 1; k < LOG; ++k) {
        matMul(mpow[k-1], mpow[k-1], mpow[k]);
    }

    // v0 для длины 2
    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];
            int val = v0[s] + 1;
            if (val >= MOD) val -= MOD;
            v0[s] = val;
        }
    }

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

    // кэш по n -> ответ
    unordered_map<long long,int> cache;
    cache.reserve(T * 2);
    cache.max_load_factor(0.7f);

    while (T--) {
        long long n;
        cin >> n;
        auto it = cache.find(n);
        if (it != cache.end()) {
            cout << it->second << '\n';
        } else {
            int ans = solve_n(n);
            cache.emplace(n, ans);
            cout << ans << '\n';
        }
    }

    return 0;
}
