#!/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()