#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

signed main() {
    int T;
    cin >> T;
    int dp[10000][10][10];
    // Инициализация нулями
    for (int i = 0; i <= 9999; i++) {
        for (int j = 0; j < 10; j++) {
            for (int k = 0; k < 10; k++) {
                dp[i][j][k] = 0;
            }
        }
    }
    for (int i = 1; i < 10; i++) {          // первая цифра
        for (int j = 0; j < 10; j++) {      // вторая цифра
            for (int k = 0; k < 10; k++) {  // третья цифра
                if (gcd(i, j) != gcd(j, k)) {
                    dp[3][gcd(j, k)][k]++;
                }
            }
        }
    }
    for (int N = 4; N <= 9999; N++) {
        for (int g = 0; g < 10; g++) {
            for (int last = 0; last < 10; last++) {
                if (dp[N - 1][g][last] == 0) continue;
                for (int digit = 0; digit < 10; digit++) {
                    int new_g = gcd(last, digit);
                    if (g != new_g) {
                        dp[N][new_g][digit] = (dp[N][new_g][digit] + dp[N - 1][g][last]) % MOD;
                    }
                }
            }
        }
    }
    while (T--) {
        int n;
        cin >> n;
        int ans = 0;
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < 10; j++) {
                ans = (ans + dp[n][i][j]) % MOD;
            }
        }
        cout << ans << endl;
    }
    return 0;
}