#include <iostream>
#include <iomanip>
#include <math.h>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cassert>
#include <deque>
#include <queue>
#include <vector>
#include <stack>
#include <string>
#include <fstream>
#include <ctime>
#include <numeric>

using namespace std;

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2")

#define int long long
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define vec vector
#define pb push_back

const int INF = 1e9;
const int MOD = 1e9 + 7;
const int SZ = 33;

struct Matrix {
    int mat[SZ][SZ];
    Matrix() {
        for (int i = 0; i < SZ; ++i)
            for (int j = 0; j < SZ; ++j)
                mat[i][j] = 0;
    }
};

vector<pair<int, int>> states;
int state_id[10][10];
vec<Matrix> powers(62);
vec<int> start_vec(SZ);

Matrix mat_mul(const Matrix& A, const Matrix& B) {
    Matrix C;
    for (int i = 0; i < SZ; ++i) {
        for (int k = 0; k < SZ; ++k) {
            if (A.mat[i][k] == 0) continue;
            for (int j = 0; j < SZ; ++j) {
                C.mat[i][j] = (C.mat[i][j] + A.mat[i][k] * B.mat[k][j]) % MOD;
            }
        }
    }
    return C;
}

void vec_mul(vec<int>& v_in, Matrix & M, vec<int>& v_out) {
    for (int j = 0; j < SZ; ++j) {
        int sum = 0;
        for (int i = 0; i < SZ; ++i) {
            if (v_in[i]) {
                sum = (sum + v_in[i] * M.mat[i][j]) % MOD;
            }
        }
        v_out[j] = sum;
    }
}

void precompute() {
    int k = 0;
    for (int u = 0; u < 10; ++u) {
        for (int g = 0; g < 10; ++g) {
            state_id[u][g] = -1;
            bool possible = false;
            if (u == 0) possible = true;
            else {
                if (g > 0 && u % g == 0) possible = true;
            }
            if (possible) {
                state_id[u][g] = k;
                states.push_back({u, g});
                k++;
            }
        }
    }

    Matrix M;
    for (int i = 0; i < SZ; ++i) {
        int u = states[i].first;
        int g = states[i].second;
        for (int v = 0; v < 10; ++v) {
            int new_g = std::gcd(u, v);
            if (new_g != g) {
                int j = state_id[v][new_g];
                if (j != -1) {
                    M.mat[i][j]++;
                }
            }
        }
    }
    powers[0] = M;
    for (int i = 1; i < 62; ++i) {
        powers[i] = mat_mul(powers[i - 1], powers[i - 1]);
    }
    for (int i = 0; i < SZ; ++i) start_vec[i] = 0;
    for (int a1 = 1; a1 < 10; ++a1) {
        for (int a2 = 0; a2 < 10; ++a2) {
            int g = std::gcd(a1, a2);
            int idx = state_id[a2][g];
            if (idx != -1) {
                start_vec[idx]++;
            }
        }
    }
}

void solve() {
    int n;
    cin >> n;
    if (n == 2) {
        cout << 90 << endl;
        return;
    }
    vec<int> current_vec(SZ), next_vec(SZ);
    for (int i = 0; i < SZ; ++i) {
        current_vec[i] = start_vec[i];
    }
    int steps = n - 2;
    for (int i = 0; i < 62; ++i) {
        if ((steps >> i) & 1) {
            vec_mul(current_vec, powers[i], next_vec);
            for (int j = 0; j < SZ; ++j) current_vec[j] = next_vec[j];
        }
    }
    int ans = 0;
    for (int i = 0; i < SZ; ++i) {
        ans = (ans + current_vec[i]) % MOD;
    }
    cout << ans << endl;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    precompute();
    int t = 1; cin >> t;
    for (; t > 0; --t) {
        solve();
    }
}