bool isPrime(long n) {
    if (n <= 1)
        return false;
    if (n == 2)
        return true;
    if (n % 2 == 0)
        return false;
    long sqrtN = sqrt(n);
    for (long i = 3; i <= sqrtN; i += 2) {
        if (n % i == 0)
            return false;
    }
    return true;
}

bool SumOfDigits(string number, int k) {
    for (size_t i = 0; i <= number.size() - k; ++i) {
        int sum = 0;
        for (int j = 0; j < k; ++j) {
            sum += (number[i + j] - '0');
        }
        if (!isPrime(sum)) {
            return false;
        }
    }
    return true;
}

string filler(int n, int k) {
    return to_string(static_cast<long>(pow(10, k)) + n).erase(0, 1);
}

void dehaka(vector<long>& result) {
    vector<long> cache(10000);
    vector<pair<pair<int, long>, vector<int>>> D;
    for (int k = 0; k <= 9999; k++) {
        if (SumOfDigits(filler(k, 4), 3) and SumOfDigits(filler(k, 4), 4)) {
            if (k >= 1000) cache[k] = 1;
            vector<int> temp;
            for (int i = 0; i <= 9; i++) {
                string S = filler(i * 1000 + k / 10, 4);
                if (SumOfDigits(S, 3) and SumOfDigits(S, 4) and SumOfDigits(filler(i * 10000 + k, 5), 5)) temp.push_back(i * 1000 + k / 10);
            }
            if (!temp.empty()) D.push_back({ {k, 0}, temp });
        }
    }
    for (int n = 5; n <= 400000; n++) {
        long total = 0;
        for (int i = 0; i < D.size(); i++) {
            long sum = 0;
            for (int K : D[i].second) sum = (sum + cache[K]) % 1000000007;
            D[i].first.second = sum;
            total = (total + sum) % 1000000007;
        }
        if (n == 5) fill(cache.begin(), cache.end(), 0);
        for (int i = 0; i < D.size(); i++) cache[D[i].first.first] = D[i].first.second;
        result.push_back(total);
    }
}

int main()
{
    vector<long> result = { 0, 9, 90, 303, 280 };
    dehaka(result);
    int q, n;
    cin >> q;
    for (int i = 1; i <= q; i++) {
        cin >> n;
        cout << result[n] << '\n';
    }
}