#!/bin/python3

import math
import os
import random
import re
import sys

#
# Complete the 'primeDigitSums' function below.
#
# The function is expected to return an INTEGER.
# The function accepts INTEGER n as parameter.
#
_arr = []
_sum3=set()
_sum4=set()
_sum5=set()
_primes=[]

def _is_prime_trial_division(n):   
    return int(n) in _sum3 or int(n) in _sum4 or int(n) in _sum5
    
def _build_prime_trial_division():
    for i in range(0, 10**3-1):
        if _primes[sum([int(x) for x in list(str(i))])]:
            _sum3.add(i)
    for i in _sum3:
        for j in range(10):
            if _primes[i+j]:
                _sum4.add(int(str(i)+str(j)))
    for i in _sum4:
        for j in range(10):
            if _primes[i+j]:
                _sum5.add(int(str(i)+str(j)))

    

def _build_sieve_of_eratosthenes(limit):
    global _primes
    _primes = [True] * (limit + 1)
    p = 2
    while p * p <= limit:
        if _primes[p]:
            for i in range(p * p, limit + 1, p):
                _primes[i] = False
        p += 1
    
    
def _prime_sum(x):
    x=str(x)
    for i in range(len(x)-5):
        if not _is_prime_trial_division(x[i: i+5]):
            return False
    for i in range(len(x)-4):
        if not _is_prime_trial_division(x[i: i+4]):
            return False
    for i in range(len(x)-3):
        if not _is_prime_trial_division(x[i: i+3]):
            return False
                   
    print(x)
    return True
            
            
        
def primeDigitSums(n):
    _build_sieve_of_eratosthenes(10**5)
    _build_prime_trial_division()

    count=0
    for i in range(10**(n), 10**(n+1)-1):
        if _prime_sum(i):
            count+=1
 
    return count
    # Write your code here


if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    q = int(input().strip())

    for q_itr in range(q):
        n = int(input().strip())

        result = primeDigitSums(n)

        fptr.write(str(result) + '\n')

    fptr.close()

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';
    }
}