#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pii = pair<int, int>;

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

template <uint32_t MOD>
struct ModularInt {
    int x = 0;

    ModularInt() {}

    ModularInt(int x) : x(x < 0 ? x + MOD : x % MOD) {}

    ModularInt(const ModularInt &other) : x(other.x) {}

    ModularInt operator+=(const ModularInt &other) {
        x += other.x;
        if (x >= MOD)
            x -= MOD;
        return *this;
    }

    ModularInt operator*=(const ModularInt &other) {
        x = ((ll)x * other.x) % MOD;
        return *this;
    }

    friend ModularInt operator+(const ModularInt &a, const ModularInt &b) {
        return ModularInt(a) += b;
    }

    friend ModularInt operator*(const ModularInt &a, const ModularInt &b) {
        return ModularInt(a) *= b;
    }

    friend ostream& operator<<(ostream& out, const ModularInt& other) {
        return out << other.x;
    }
};

const int mod = 1e9 + 7;
using mint = ModularInt<mod>;

using matrix = vector<vector<mint>>;

matrix identity_matrix(int n) {
    matrix a(n, vector<mint>(n));
    for (int i = 0; i < n; i++)
        a[i][i] = 1;
    return a;
}

matrix matmul(const matrix &a, const matrix &b) {
    int n = a.size();
    matrix c(n, vector<mint>(n));
    for (int i = 0; i < n; i++)
        for (int k = 0; k < n; k++)
            for (int j = 0; j < n; j++)
                c[i][j] += a[i][k] * b[k][j];
    return c;
}

matrix binpow(matrix a, ll pw) {
    int n = a.size();
    matrix b = identity_matrix(n);
    for (; pw; pw >>= 1, a = matmul(a, a))
        if (pw & 1)
            b = matmul(b, a);
    return b;
}

int Gcd[10][10];

vector<pii> states;
vector<mint> base(33);
vector<matrix> pws;

void precalc() {
    for (int d = 0; d < 10; d++)
        for (int g = 0; g < 10; g++)
            if ((g == 0 && d == 0) || (g != 0 && d % g == 0))
                states.push_back({d, g});
    for (int d1 = 1; d1 < 10; d1++)
        for (int d2 = 0; d2 < 10; d2++) {
            pii st = {d2, Gcd[d1][d2]};
            int p = find(all(states), st) - states.begin();
            base[p] += 1;
        }
    matrix transition(33, vector<mint>(33));
    for (int v = 0; v < 33; v++) {
        auto [d1, g] = states[v];
        for (int d2 = 0; d2 < 10; d2++)
            if (Gcd[d1][d2] != g) {
                pii st = {d2, Gcd[d1][d2]};
                int u = find(all(states), st) - states.begin();
                transition[v][u] += 1;
            }
    }
    for (int i = 0; i < 61; i++) {
        pws.push_back(transition);
        transition = matmul(transition, transition);
    }
}

inline void solve() {
    long long n;
    cin >> n;
    n -= 2;
    vector<mint> dp = base;
    vector<mint> dp1(33);
    for (int b = 0; b < 60; b++)
        if ((n >> b) & 1) {
            fill(all(dp1), 0);
            for (int i = 0; i < 33; i++)
                for (int j = 0; j < 33; j++)
                    dp1[j] += dp[i] * pws[b][i][j];
            swap(dp, dp1);
        }
    cout << accumulate(all(dp), mint(0)) << '\n';
}

signed main() {
    for (int d = 0; d < 10; d++)
        for (int e = 0; e < 10; e++)
            Gcd[d][e] = __gcd(d, e);
    precalc();
#ifdef _DEBUG
    freopen("01.dat", "r", stdin);
#endif
    int tt = 1;
    cin >> tt;
    for (int test_id = 1; test_id <= tt; test_id++) {
#ifdef _DEBUG
        cout << "Case #" << test_id << ":\n";
#endif
        solve();
    }
    return 0;
}
