Chloe is fascinated by prime numbers. She came across the number $283002$ on a sign and, though the number is not prime, found some primes hiding in it by using the following rules:  

Every three consecutive digits sum to a prime:
$\underbrace{283}002\quad\underbrace{2830}02\quad28\underbrace{300}2\quad283\underbrace{002}$
Every four consecutive digits sum to a prime:
$\underbrace{28300}2\quad\underbrace{28300}2\quad28\underbrace{3002}$
Every five consecutive digits sum to a prime:
$\underbrace{283002}\quad2\underbrace{83002}$

You must answer $\textit{q}$ queries, where each query consists of an integer, $n$. For each $n$, find and print the number of positive $n$-digit numbers, modulo $10^9+7$, that satisfy all three of Chloe's rules (i.e., every three, four, and five consecutive digits sum to a prime).

Input Format

The first line contains an integer, $\textit{q}$, denoting the number of queries. 

Each of the $\textit{q}$ subsequent lines contains an integer denoting the value of $n$ for a query.  

Constraints

$1\leq q\leq2\times10^4$  
$1\leq n\leq4\times10^5$  

Output Format

For each query, print the number of $n$-digit numbers satisfying Chloe's rules, modulo $10^9+7$, on a new line.   

Sample Input 0
1
6

Sample Output 0
95

Explanation 0

There are $95$ six-digit numbers satisfying the property above, where the respective first and last ones are $\textbf{101101}$ and $\boldsymbol{902005}$.

Source: hackerrank | Difficulty: MEDIUM
Tags: Dynamic programming


Solutions:
from itertools import product
from collections import defaultdict
import sys
M = 1000000007
p = set([2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43])

def good(a, b, c, d, e):
	if not a + b + c in p:
		return False
	if not b + c + d in p:
		return False
	if not c + d + e in p:
		return False
	if not a + b + c + d in p:
		return False
	if not b + c + d + e in p:
		return False
	if not a + b + c + d + e in p:
		return False
	return True

def con(a, b, c, d, e):
	return e + 10 * d + 100 * c + 1000 * b + 10000 * a
goods = defaultdict(list)
curr = defaultdict(int)
for (a, b, c, d, e) in product(range(10), repeat=5):
	if good(a, b, c, d, e):
		goods[con(0, a, b, c, d)].append(e)
		if a > 0:
			curr[con(a, b, c, d, e)] = 1
lim = 400001
ans = [0 for _ in range(lim + 1)]
ans[5] = len(curr.items())
ans[1] = 9
ans[2] = 90
for (a, b, c) in product(range(1, 10), range(10), range(10)):
	if a + b + c in p:
		ans[3] += 1
for (a, b, c, d) in product(range(1, 10), range(10), range(10), range(10)):
	if a + b + c in p and b + c + d in p and (a + b + c + d in p):
		ans[4] += 1
for n in range(6, 100):
	newcurr = defaultdict(int)
	if n == lim:
		print([i for (i, v) in curr.items()])
	for (num, value) in curr.items():
		for f in goods[num % 10000]:
			k = 10 * (num % 10000) + f
			newcurr[k] = (newcurr[k] + value) % M
			ans[n] = (ans[n] + value) % M
	curr = newcurr
(hsh, invhsh, h) = (defaultdict(int), defaultdict(int), 0)
currl = []
for (i, v) in curr.items():
	currl.append(v)
	hsh[i] = h
	invhsh[h] = i
	h += 1
for n in range(100, lim + 1):
	currl = [(currl[34] + currl[56]) % M, currl[48], currl[17], currl[17], currl[43], currl[55], (currl[9] + currl[31]) % M, currl[43], currl[54], currl[7], currl[12], currl[7], currl[37], currl[54], currl[54], currl[41], currl[66], currl[48], currl[53], currl[66], currl[46], currl[53], currl[65], currl[65], currl[8], (currl[36] + currl[57]) % M, currl[46], currl[65], currl[53], currl[53], currl[20], currl[47], (currl[58] + currl[60]) % M, currl[20], currl[1], currl[1], currl[32], currl[47], currl[1], currl[1], (currl[36] + currl[57]) % M, (currl[36] + currl[57]) % M, (currl[22] + currl[44]) % M, (currl[36] + currl[57]) % M, currl[62], currl[4], (currl[36] + currl[57]) % M, currl[50], (currl[10] + currl[25] + currl[67]) % M, currl[62], (currl[10] + currl[25] + currl[67]) % M, currl[4], currl[55], currl[50], currl[40], currl[40], currl[15], currl[6], currl[65], currl[15], currl[62], currl[47], currl[41], currl[30], currl[26], currl[48], currl[41], currl[42], currl[47], currl[17], currl[17]]
	ans[n] = sum(currl) % M
for _ in range(int(input())):
	sys.stdout.write(str(ans[int(input())]) + '\n')


import sys
primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43}

def canextend(l, s):
	(s, l) = (s + l % 10, l // 10)
	(s, l) = (s + l % 10, l // 10)
	if not s in primes:
		return False
	(s, l) = (s + l % 10, l // 10)
	if not s in primes:
		return False
	(s, l) = (s + l % 10, l // 10)
	if not s in primes:
		return False
	return True
last4digitmap = []
for i in range(10000):
	followups = []
	for j in range(10):
		if canextend(i, j):
			followups.append(i % 1000 * 10 + j)
	last4digitmap.append(followups)

def extend1(resultsofar):
	result = {}
	for (k, v) in resultsofar.items():
		for n in last4digitmap[k]:
			result[n] = result.setdefault(n, 0) + v
	return result

def good4(x):
	(a, x) = (x % 10, x // 10)
	(b, x) = (x % 10, x // 10)
	(c, x) = (x % 10, x // 10)
	d = x
	return a + b + c + d in primes and a + b + c in primes and (b + c + d in primes)
l = {x: 1 for x in range(1000, 10000) if good4(x)}
q = int(input().strip())
queries = []
for a0 in range(q):
	n = int(input().strip())
	queries.append(n)
todo = sorted(queries)
while todo[0] < 5:
	todo.pop(0)
cache = [0] * 400001
cache[1] = len(range(1, 10))
cache[2] = len(range(10, 100))
cache[3] = len([i for i in range(100, 1000) if sum([int(x) for x in str(i)]) in primes])
cache[4] = len([i for i in range(1000, 10000) if sum([int(x) for x in str(i)]) in primes and sum([int(x) for x in str(i)[:3]]) in primes and (sum([int(x) for x in str(i)[-3:]]) in primes)])
lastlength = 4
l = {x: 1 for x in range(1000, 10000) if good4(x)}
for stringlength in todo:
	stepstodo = stringlength - lastlength
	while stepstodo >= 1:
		l = extend1(l)
		stepstodo -= 1
	s = 0
	for (k, v) in l.items():
		l[k] = v % 1000000007
		s += v
	cache[stringlength] = s % 1000000007
	lastlength = stringlength
for n in queries:
	print(cache[n])


import sys
MAXJUMP = 17
MODULUS = 10 ** 9 + 7
PT = [False] * 46
(PT[2], PT[3], PT[5], PT[7], PT[11]) = (True, True, True, True, True)
(PT[13], PT[17], PT[19], PT[23], PT[29]) = (True, True, True, True, True)
(PT[31], PT[37], PT[41], PT[43]) = (True, True, True, True)

def is_prime(n):
	return PT[n]

def prime_property(digits, full_check=False):
	n = len(digits)
	for j in range(0 if full_check else n - 3, n - 2):
		k = j + 3
		if not is_prime(sum(digits[j:k])):
			return False
	for j in range(0 if full_check else n - 4, n - 3):
		k = j + 4
		if not is_prime(sum(digits[j:k])):
			return False
	for j in range(0 if full_check else n - 5, n - 4):
		k = j + 5
		if not is_prime(sum(digits[j:k])):
			return False
	return True

def check_property(n, solutions=[], digits=[], depth=0, full_check=False):
	if depth == 0:
		solutions = []
		digits = [0] * n
		for digits[depth] in range(0 if full_check else 1, 10):
			solutions = check_property(n, solutions, digits, depth + 1)
	elif depth < n:
		for digits[depth] in range(0, 10):
			solutions = check_property(n, solutions, digits, depth + 1)
	elif prime_property(digits, True):
		solutions.append(list(digits))
	return solutions

def check_recursive(prev_solutions):
	solutions = []
	for prev in prev_solutions:
		for lastdigit in range(0, 10):
			cur = list(prev) + [lastdigit]
			if prime_property(cur):
				solutions.append(list(cur))
	return solutions

def convert_to_sparse(L):
	return {L[i]: 1 for i in range(len(L))}
lookup = {0: 0, 1: 9, 2: 90, 3: 303, 4: 280, 5: 218}
translation = {6656: 336, 2050: 88, 6148: 171, 2902: 116, 4102: 126, 2056: 89, 4106: 127, 6146: 170, 6160: 173, 8210: 349, 20: 0, 21: 6, 6166: 175, 23: 11, 4120: 129, 25: 16, 4124: 130, 29: 20, 30: 25, 32: 30, 6320: 250, 34: 35, 38: 39, 2092: 90, 4616: 283, 2098: 91, 52: 49, 8542: 218, 2102: 92, 2104: 93, 58: 58, 4160: 132, 2230: 239, 70: 62, 2120: 94, 74: 66, 76: 71, 1101: 76, 2128: 96, 6670: 337, 1110: 78, 4184: 135, 2140: 97, 6238: 313, 8698: 358, 2146: 98, 6250: 314, 8300: 204, 6254: 315, 111: 77, 6256: 316, 4210: 274, 8308: 206, 4214: 275, 120: 79, 6164: 174, 122: 231, 124: 263, 6506: 179, 3200: 124, 2182: 99, 140: 233, 6850: 341, 142: 299, 6290: 317, 148: 300, 4250: 276, 346: 38, 160: 265, 8560: 220, 2210: 237, 164: 302, 166: 266, 8362: 211, 1200: 80, 4274: 278, 6326: 251, 8380: 213, 6340: 285, 200: 1, 201: 2, 6346: 286, 203: 3, 4300: 137, 205: 4, 4304: 138, 209: 5, 210: 7, 212: 8, 214: 9, 218: 10, 8212: 350, 8416: 353, 8230: 351, 230: 12, 232: 13, 380: 40, 6380: 253, 238: 15, 4340: 140, 382: 41, 4346: 141, 2300: 101, 2302: 102, 256: 19, 6016: 301, 2308: 103, 6410: 319, 4364: 143, 6416: 321, 6418: 322, 2326: 105, 8410: 352, 6430: 323, 6704: 194, 290: 21, 6436: 325, 296: 23, 298: 24, 300: 26, 50: 44, 302: 27, 304: 28, 308: 29, 2362: 106, 320: 31, 322: 32, 6470: 326, 6472: 327, 6476: 328, 4430: 281, 56: 53, 2386: 109, 340: 36, 344: 37, 6490: 329, 6494: 330, 6500: 177, 6502: 178, 2410: 240, 6508: 180, 2416: 241, 6520: 182, 6832: 340, 6524: 183, 6526: 184, 386: 42, 388: 43, 6140: 168, 236: 14, 2452: 242, 4676: 288, 410: 125, 412: 128, 2458: 245, 416: 131, 418: 134, 4166: 133, 6566: 188, 4520: 243, 8092: 348, 2476: 248, 4526: 244, 2632: 249, 434: 139, 436: 142, 6584: 191, 2122: 95, 6560: 186, 2500: 110, 2506: 111, 6562: 187, 4856: 295, 6610: 331, 470: 144, 6616: 333, 6052: 304, 476: 149, 250: 17, 478: 152, 5200: 163, 4580: 246, 2470: 247, 2812: 258, 490: 154, 8302: 205, 2542: 112, 496: 159, 562: 55, 500: 45, 254: 18, 502: 46, 6650: 334, 6652: 335, 2560: 114, 4610: 282, 4694: 289, 2566: 115, 520: 50, 940: 272, 524: 51, 526: 52, 6232: 311, 6674: 338, 430: 136, 8452: 354, 4634: 284, 2650: 254, 8740: 297, 6236: 312, 6700: 193, 560: 54, 6920: 257, 6706: 195, 566: 56, 568: 57, 6580: 190, 4670: 287, 580: 59, 584: 60, 6412: 320, 586: 61, 610: 164, 2638: 252, 8632: 356, 6740: 197, 6742: 198, 6746: 199, 4700: 145, 3002: 122, 2656: 255, 2320: 104, 4706: 146, 614: 167, 616: 172, 6764: 202, 6760: 201, 4724: 148, 8830: 362, 2692: 256, 8470: 355, 8812: 361, 650: 176, 652: 181, 656: 185, 658: 189, 110: 75, 4760: 150, 4766: 151, 674: 196, 676: 200, 6830: 339, 4784: 153, 2740: 279, 2746: 280, 700: 63, 8650: 357, 704: 64, 706: 65, 8902: 222, 3020: 123, 6434: 324, 4814: 291, 8920: 224, 292: 22, 6230: 310, 740: 67, 742: 68, 746: 69, 748: 70, 6896: 342, 4850: 294, 760: 72, 764: 73, 766: 74, 8320: 208, 6614: 332, 8968: 226, 4874: 296, 2830: 260, 472: 147, 6940: 290, 8326: 209, 4904: 155, 128: 232, 8500: 215, 9020: 261, 830: 203, 832: 207, 836: 210, 838: 212, 2188: 100, 6986: 360, 4940: 157, 4946: 158, 854: 217, 856: 219, 2908: 117, 8506: 216, 8030: 343, 8032: 344, 4964: 160, 8038: 345, 2920: 118, 146: 234, 2926: 119, 8050: 346, 8056: 347, 6292: 318, 890: 221, 892: 223, 6014: 298, 896: 225, 2368: 107, 5002: 161, 2962: 120, 494: 156, 920: 227, 6980: 359, 5020: 162, 926: 235, 2032: 86, 6050: 303, 2980: 121, 326: 33, 6056: 305, 6058: 306, 4012: 262, 4016: 264, 328: 34, 946: 273, 670: 192, 6070: 307, 8120: 259, 2548: 113, 6074: 308, 6076: 309, 4030: 267, 4256: 277, 4034: 268, 2380: 108, 8140: 292, 8146: 293, 2003: 81, 980: 236, 2005: 82, 6104: 165, 2212: 238, 6106: 166, 2012: 83, 506: 47, 2014: 84, 4070: 269, 508: 48, 4076: 270, 850: 214, 2030: 85, 9200: 228, 1011: 229, 6142: 169, 2038: 87, 1020: 230, 4094: 271}
table = [[1, 2, 3, 4, 5], [81, 82], [83, 84], [85, 86, 87], [88, 89], [90, 91], [7, 8, 9, 10], [92, 93], [94, 95, 96], [97, 98], [99, 100], [12, 13, 14, 15], [101, 102, 103], [104, 105], [106, 107], [108, 109], [17, 18, 19], [110, 111], [112, 113], [114, 115], [21, 22, 23, 24], [116, 117], [118, 119], [120], [121], [26, 27, 28, 29], [122], [123], [], [], [31, 32, 33, 34], [124], [], [], [], [36, 37, 38], [], [], [], [40, 41, 42, 43], [], [], [], [], [45, 46, 47, 48], [161], [162], [], [], [50, 51, 52], [163], [], [], [54, 55, 56, 57], [], [], [], [], [59, 60, 61], [], [], [], [63, 64, 65], [], [], [], [67, 68, 69, 70], [], [], [], [], [72, 73, 74], [], [], [], [76], [], [78], [], [80], [], [25, 30, 39], [44, 53], [79, 231, 232], [233, 234], [26, 27, 29], [31, 33], [40, 42], [45, 47], [54, 56], [227, 235], [236], [230], [], [80], [], [], [], [], [], [], [122], [123], [], [124], [], [], [], [], [], [], [], [], [], [], [], [261], [], [228], [], [], [], [0], [1], [], [126, 127], [230], [], [129, 130], [80], [], [132, 133], [], [], [135], [], [137, 138], [], [], [140, 141], [], [], [143], [], [145, 146], [], [], [148], [], [150, 151], [], [], [153], [], [155], [], [157, 158], [], [], [160], [], [0], [1], [], [165, 166], [], [], [168, 169, 170, 171], [], [], [], [], [173, 174, 175], [], [], [], [177, 178, 179, 180], [161], [162], [], [], [182, 183, 184], [163], [], [], [186, 187, 188], [], [], [], [190, 191], [], [], [193, 194, 195], [], [], [], [197, 198, 199], [], [], [], [201, 202], [], [], [204, 205, 206], [122], [123], [], [208, 209], [124], [], [211], [], [213], [], [215, 216], [], [], [218], [], [220], [], [222], [261], [224], [228], [226], [], [228], [], [75], [1], [], [], [], [], [], [], [92], [94], [101], [127], [132, 133], [243, 244], [163], [], [246], [], [145, 146], [150], [250, 251], [124], [], [253], [], [177, 179], [186], [257], [228], [259], [80], [204], [1], [79, 263], [], [265, 266], [], [], [26, 28], [36, 38], [63, 65], [72, 74], [272, 273], [], [], [93], [97, 98], [110, 111], [114, 115], [279, 280], [], [], [137], [166], [173, 175], [285, 286], [], [], [193, 195], [201], [290], [], [292, 293], [], [], [215, 216], [220], [297], [], [233, 299, 234, 300], [], [], [265, 302, 266], [], [45, 46, 47, 48], [50, 51, 52], [54, 55, 56], [59, 60], [63, 64, 65], [67, 68, 69], [72, 73], [101, 102, 103], [104, 105], [106], [108], [110, 111], [112], [114], [116], [118], [126, 127], [129, 130], [132, 133], [135], [137, 138], [140, 141], [143], [145, 146], [148], [150, 151], [155], [157, 158], [165, 166], [168, 169, 170], [173, 174], [177, 178, 179], [182, 183], [186, 188], [193, 194], [197, 199], [204, 205], [208], [215], [226], [26, 27, 29], [31, 33], [40], [45, 47], [54], [227], [92], [94], [101], [127], [132], [243], [145], [250], [177], [359, 360], [], [], [259], [204], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], []]
ans = [2, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 3, 2, 1, 2, 1, 2, 0, 2, 0, 0, 1, 0, 1, 1, 2, 0, 1, 0, 1, 3, 1, 3, 1, 0, 1, 1, 1, 1, 3, 1, 2, 0, 0, 1, 1, 0, 0, 2, 1, 2, 0, 1, 1, 1, 0, 0, 2, 1, 1, 1, 0, 0, 0, 2, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1, 2, 0, 0, 1, 1, 0, 0, 3, 1, 1, 1, 1, 1, 0, 1, 0, 2, 2, 1, 0, 2, 1, 1, 0, 1, 0, 0, 0, 2, 2, 3, 0, 1, 3, 0, 1, 1, 0, 3, 2, 0, 1, 0, 2, 1, 0, 1, 1, 0, 1, 0, 3, 2, 0, 1, 0, 2, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 2, 0, 1, 2, 0, 1, 1, 1, 0, 0, 2, 1, 1, 0, 3, 1, 2, 0, 0, 1, 1, 0, 0, 2, 0, 1, 0, 0, 0, 0, 2, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 3, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 2, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 2, 3, 0, 2, 1, 1, 2, 2, 1, 1, 0, 0, 0, 0, 0, 0, 2, 1, 0, 1, 0, 0, 0, 2, 1, 0, 1, 0, 0, 0, 1, 0, 2, 0, 2, 0, 1, 0, 2, 2, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0]
shrink_translation = {}
grow_translation = {}
sources = []
destinations = []
for i in range(len(table)):
	if table[i]:
		sources.append(i)
	for j in table[i]:
		destinations.append(j)
both_source_dest = sorted(set(destinations).intersection(sources))
for i in range(len(both_source_dest)):
	shrink_translation[both_source_dest[i]] = i
	grow_translation[i] = both_source_dest[i]
shrunk_ans = [0] * len(both_source_dest)
for i in range(len(ans)):
	if shrink_translation.get(i, -1) != -1:
		shrunk_ans[shrink_translation[i]] = shrink_translation[ans[i]]
shrunk_table = []
for i in range(len(both_source_dest)):
	shrunk_table.append({})
for i in range(len(table)):
	if shrink_translation.get(i, -1) != -1:
		for j in table[i]:
			if shrink_translation.get(j, -1) != -1:
				shrunk_table[shrink_translation[i]][shrink_translation[j]] = 1
dense_table = []
dense_table.append(shrunk_table)
for dense_index in range(1, MAXJUMP):
	dense_table.append([])
	for i in range(len(dense_table[dense_index - 1])):
		dense_table[dense_index].append({})
	for i in range(len(dense_table[dense_index - 1])):
		for j in range(len(dense_table[dense_index - 1])):
			value = int(0)
			for k in range(len(dense_table[dense_index - 1])):
				value += int(dense_table[dense_index - 1][i].get(k, 0) * dense_table[dense_index - 1][k].get(j, 0))
			if value:
				dense_table[dense_index][i][j] = int(value % MODULUS)

def get_full_ans(shrunk_ans):
	total_answer = 0
	for i in range(len(table)):
		if shrink_translation.get(i, -1) != -1 and shrunk_ans[shrink_translation[i]]:
			for next_k in table[i]:
				total_answer += shrunk_ans[shrink_translation[i]]
			total_answer = total_answer % MODULUS
	return total_answer
q = int(input().strip())
queries = []
for a0 in range(q):
	n = int(input().strip())
	queries.append(n)
sorted_queries = sorted(queries)
index = 0
while sorted_queries[index] < 6:
	index += 1
n = 5
while index < len(sorted_queries):
	for jump in reversed(range(MAXJUMP)):
		if sorted_queries[index] >= n + 2 ** jump + 1:
			n += 2 ** jump
			next_shrunk_ans = [0 for _ in range(len(both_source_dest))]
			for i in range(len(shrunk_ans)):
				if shrunk_ans[i]:
					for (next_k, v) in dense_table[jump][i].items():
						next_shrunk_ans[next_k] += shrunk_ans[i] * v % MODULUS
			shrunk_ans = next_shrunk_ans
	if sorted_queries[index] == n + 1:
		lookup[n + 1] = get_full_ans(shrunk_ans) % MODULUS
		index += 1
for query in queries:
	print(lookup[query])


from math import sqrt
from collections import Counter
import sys
import datetime
import gc
from collections import defaultdict

def getSive(n):
	size = int(sqrt(n))
	result = [1] * (n + 1)
	for i in range(2, size + 1):
		limit = n // i
		for j in range(2, limit + 1):
			result[i * j] = 0
	result[0] = 0
	result[1] = 0
	return result

def isPrime(i, primes):
	sum = 0
	while i > 0:
		sum += i % 10
		i = i // 10
	return primes[sum]

def getSum(i):
	sum = 0
	while i > 0:
		sum += i % 10
		i = i // 10
	return sum

def getTop1000(primes):
	result = [i for i in range(10 ** 3, 10 ** 4) if isPrime(i, primes) and isPrime(i // 10, primes) and isPrime(i % 1000, primes)]
	return result
q = int(input().strip())
primes = getSive(45)
top1K = getTop1000(primes)
current = {n: 1 for n in top1K}
preComputedSums = {n: getSum(n) for n in range(10 ** 4)}
modulo = 10 ** 9 + 7
news_keys = None
ns = list()
for a0 in range(q):
	ns.append(int(input().strip()))
cache_size = max(ns) + 4
cache = [0] * cache_size
cache[0] = 0
cache[1] = 9
cache[2] = 90
cache[3] = len([i for i in range(100, 1000) if isPrime(i, primes)])
cache[4] = len(current)
reach57 = False
for _t in range(5, cache_size):
	if reach57 and news_keys:
		next = dict.fromkeys(keys, 0)
		for k_v in news_keys:
			next[k_v[1]] += current[k_v[0]]
	else:
		next = defaultdict(int)
		if reach57 and news_keys == None:
			news_keys = list()
		for (k, v) in current.items():
			s4 = preComputedSums[k]
			s3 = preComputedSums[k % 1000]
			s2 = preComputedSums[k % 100]
			for new in range(10):
				if primes[s4 + new] and primes[s3 + new] and primes[s2 + new]:
					next_key = k % 1000 * 10 + new
					next[next_key] += v
					if news_keys != None:
						news_keys.append([k, next_key])
		if news_keys != None:
			keys = next.keys()
	if _t % 20 == 0:
		for (k, v) in next.items():
			next[k] = v % modulo
	if not reach57 and len(next.keys()) == 57:
		reach57 = True
	current = next
	cache[_t] = sum(current.values()) % modulo
for _t in ns:
	print(cache[_t])
gc.enable()


import collections
PRIMES = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43}
MOD_VALUE = 10 ** 9 + 7

def num_3_digits():
	result = 0
	for a in range(1, 10):
		for b in range(10):
			for c in range(10):
				if a + b + c in PRIMES:
					result += 1
	return result

def num_4_digits():
	result = 0
	for a in range(1, 10):
		for b in range(10):
			for c in range(10):
				for d in range(10):
					if a + b + c in PRIMES and b + c + d in PRIMES and (a + b + c + d in PRIMES):
						result += 1
	return result

class ChloeNumSet:

	def __init__(self):
		self._tails = collections.defaultdict(lambda : 0)
		self._digit_add_map = collections.defaultdict(list)
		self._num_digits = 5
		for a in range(10):
			for b in range(10):
				for c in range(10):
					for d in range(10):
						for e in range(10):
							if a + b + c in PRIMES and b + c + d in PRIMES and (c + d + e in PRIMES) and (a + b + c + d in PRIMES) and (b + c + d + e in PRIMES) and (a + b + c + d + e in PRIMES):
								self._digit_add_map['%d%d%d%d' % (a, b, c, d)].append(e)
								if a != 0:
									self._tails['%d%d%d%d' % (b, c, d, e)] += 1

	def size(self):
		return sum(self._tails.values()) % MOD_VALUE

	def evolve(self):
		if self._num_digits >= 15:
			t = self._tails
			new_tails = {'0020': (t['3002'] + t['5002']) % MOD_VALUE, '0030': t['2003'], '0032': t['2003'], '0038': t['2003'], '0050': t['2005'], '0056': t['2005'], '0120': t['2012'], '0122': t['2012'], '0128': t['2012'], '0140': t['2014'], '0146': t['2014'], '0200': (t['0020'] + t['3020'] + t['5020']) % MOD_VALUE, '0201': t['0020'], '0203': t['0020'], '0205': t['0020'], '0209': t['0020'], '0300': (t['0030'] + t['2030']) % MOD_VALUE, '0302': (t['0030'] + t['2030']) % MOD_VALUE, '0304': t['0030'], '0308': (t['0030'] + t['2030']) % MOD_VALUE, '0320': (t['0032'] + t['2032']) % MOD_VALUE, '0322': t['0032'], '0326': (t['0032'] + t['2032']) % MOD_VALUE, '0328': t['0032'], '0380': (t['0038'] + t['2038']) % MOD_VALUE, '0382': t['0038'], '0386': (t['0038'] + t['2038']) % MOD_VALUE, '0388': t['0038'], '0500': (t['0050'] + t['2050']) % MOD_VALUE, '0502': t['0050'], '0506': (t['0050'] + t['2050']) % MOD_VALUE, '0508': t['0050'], '0560': (t['0056'] + t['2056']) % MOD_VALUE, '0562': t['0056'], '0566': (t['0056'] + t['2056']) % MOD_VALUE, '0568': t['0056'], '0920': t['2092'], '0926': t['2092'], '0980': t['2098'], '1200': t['0120'], '2003': t['0200'], '2005': t['0200'], '2012': t['0201'], '2014': t['0201'], '2030': t['0203'], '2032': t['0203'], '2038': t['0203'], '2050': t['0205'], '2056': t['0205'], '2092': t['0209'], '2098': t['0209'], '3002': t['0300'], '3020': t['0302'], '3200': t['0320'], '5002': t['0500'], '5020': t['0502'], '9200': t['0920']}
			self._tails = new_tails
		else:
			new_tails = collections.defaultdict(lambda : 0)
			for (tail, count) in self._tails.items():
				if tail in self._digit_add_map:
					for digit in self._digit_add_map[tail]:
						new_tail = tail[1:] + str(digit)
						new_tails[new_tail] += count
			self._tails = {tail: count % MOD_VALUE for (tail, count) in new_tails.items()}
		self._num_digits += 1
solutions = {1: 9, 2: 90, 3: num_3_digits(), 4: num_4_digits()}
c = ChloeNumSet()
solutions[5] = c.size()
for n in range(6, 4 * 10 ** 5 + 1):
	c.evolve()
	solutions[n] = c.size()
num_queries = int(input().strip())
for _ in range(num_queries):
	n = int(input().strip())
	print(solutions[n])


import sys
from collections import defaultdict
MOD = 1000000007
primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97}
is_prime = [i in primes or i >= 64 for i in range(128)]
mult = 1 + 128 * (1 + 128 * (1 + 128 * (1 + 128)))
mat_col_memo = {}

def mat_col(t, start_digit=0):
	retv = mat_col_memo.get((t, start_digit))
	if not retv is None:
		return retv
	retv = {}
	for d in range(start_digit, 10):
		newt = t // 128 + d * mult
		if is_prime[newt % 128] and is_prime[newt // 128 % 128] and is_prime[newt // (128 * 128) % 128]:
			retv[newt] = 1
	mat_col_memo[t, start_digit] = retv
	return retv

def matf_to_vec(mat, vec):
	retv = defaultdict(lambda : 0, {})
	for (j, v) in vec.items():
		for (i, v2) in mat(j).items():
			retv[i] = (retv[i] + v * v2) % MOD
	return retv

def mat_to_vec(mat, vec):
	retv = defaultdict(lambda : 0, {})
	for (j, v) in vec.items():
		for (i, v2) in mat[j].items():
			retv[i] = (retv[i] + v * v2) % MOD
	return retv

def mat_to_straight_vec(mat, vec, out):
	for i in range(len(out)):
		out[i] = 0
	for (j, mj) in mat.items():
		v = vec[j]
		for (i, v2) in mj.items():
			out[i] += v * v2
	for i in range(len(out)):
		out[i] %= MOD

def mat_prod(mat1, mat2):
	retv = defaultdict(lambda : defaultdict(lambda : 0, {}))
	for (k, m2_k) in mat2.items():
		for (j, m1_j) in mat1.items():
			for (i, v) in m1_j.items():
				v2 = m2_k.get(j)
				if not v2 is None:
					retv[k][i] = (retv[k][i] + v * m2_k[j]) % MOD
	return retv
nums = [{64 * mult: 1}]
i = 0
while True:
	start_digit = 1 if i == 0 else 0
	i += 1
	nums.append(matf_to_vec(lambda d: mat_col(d, start_digit), nums[-1]))
	if i >= 32:
		break
mat = {k: mat_col(k, 0) for k in nums[-1].keys()}
assert all((all((k2 in mat for k2 in mat[k].keys())) for k in mat.keys()))
last_vec = nums[-1]
keys = list(last_vec.keys())
size = len(keys)
k2i = {keys[i]: i for i in range(size)}
straight_vec = [0 for _ in range(size)]
for (k, v) in last_vec.items():
	straight_vec[k2i[k]] = v
straight_mat = defaultdict(lambda : defaultdict(lambda : 0, {}))
for (i, mi) in mat.items():
	for (j, v) in mi.items():
		if v > 0:
			straight_mat[k2i[i]][k2i[j]] = v
mat_powers = {1: straight_mat}

def mpow(n):
	retv = mat_powers.get(n)
	if not retv is None:
		return retv
	if n & n - 1 == 0:
		mh = mpow(n // 2)
		retv = mat_powers[n] = mat_prod(mh, mh)
	else:
		a = n & n - 1
		b = n - a
		retv = mat_powers[n] = mat_prod(mpow(a), mpow(b))
	return retv
q = int(input())
(v1, v2) = (straight_vec.copy(), straight_vec.copy())
pows = sorted([(int(input()), i) for i in range(q)])
results = []
lastp = len(nums) - 1
(v1, v2) = (straight_vec.copy(), straight_vec.copy())
for (p, i) in pows:
	if p < len(nums):
		results.append((sum(nums[p].values()) % MOD, i))
		continue
	pw = p - lastp
	lastp = p
	pw2 = 15
	while pw > 0:
		if pw & pw2:
			mat_to_straight_vec(mpow(pw & pw2), v1, v2)
			(v1, v2) = (v2, v1)
		pw -= pw & pw2
		pw2 *= 16
	results.append((sum(v1) % MOD, i))
for (p, i) in sorted(results, key=lambda kw: kw[1]):
	print(p)


A = [0, 0, 0, 0, 0, 2, 3, 15, 2, 0]
B = [0, 0, 0, 0, 0, 4, 9, 13, 17, 2]
C = [1, 9, 90, 303, 280, 218, 95, 101, 295]
M = 10 ** 9 + 7
q = int(input())
for Q in range(q):
	n = int(input())
	for i in range(len(A), n):
		A.append(2 * (A[i - 5] + B[i - 5]) % M)
		B.append((A[i - 1] + A[i - 5] + 2 * B[i - 5]) % M)
	print(C[n] if n < len(C) else (5 * A[n - 1] + 9 * A[n - 2] + 19 * A[n - 3] + 6 * A[n - 4] + 3 * A[n - 5] + 2 * B[n - 1] + 5 * B[n - 2] + 20 * B[n - 3] + 5 * B[n - 4] + 4 * B[n - 5]) % M)


def solve(hi):
	mod = 7 + 10 ** 9
	ans = [0, 9, 90, 303, 280, 218, 95, 101, 295, 513]
	u = [2, 2, 2, 2, 2, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 2, 17, 17, 15, 15, 15, 15, 15, 15, 15, 15, 15, 6, 6, 6, 6, 4, 2, 13, 13, 13, 13, 13, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 0, 0, 0, 0]
	t = [(26, 27), (28, 29), (30, 31, 32), (33, 34), (35, 36), (37,), (38,), None, None, (39,), None, None, None, None, None, None, None, (40,), (41,), None, None, None, None, None, None, None, (43, 44, 45), (46, 47), (48, 49, 50), (51, 52), (53, 54, 55), (56, 57), (58, 59), (60, 61), (62, 63), (64, 65), (66,), (67,), (68,), None, (69,), (70,), None, (5, 6, 7, 8), (9, 10, 11, 12), (13, 14, 15, 16), (17, 18, 19, 20), (21, 22, 23, 24), (25,), None, None, None, None, (37,), (38,), None, (39,), None, None, None, (40,), None, None, None, (42,), None, None, (0, 1, 2, 3, 4), (26, 27), (0, 1, 2, 3, 4), (26, 27)]
	v = [0] * 71
	for _ in range(10, 1 + hi):
		for i in range(71):
			v[i] = 0
		for i in range(71):
			if not t[i]:
				continue
			c = u[i]
			for j in t[i]:
				v[j] = (v[j] + c) % mod
		(u, v) = (v, u)
		ans.append(sum(u) % mod)
	return ans
q = int(input())
ns = [int(input()) for _ in range(q)]
ans = solve(max(ns))
print(*(ans[n] for n in ns), sep='\n')


def solve(hi):
	mod = 7 + 10 ** 9
	ans = [0, 9, 90, 303, 280, 218, 95, 101, 295, 513]
	u = [2, 2, 2, 2, 2, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 2, 17, 17, 15, 15, 15, 15, 15, 15, 15, 15, 15, 6, 6, 6, 6, 4, 2, 13, 13, 13, 13, 13, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 0, 0, 0, 0]
	t = [(26, 27), (28, 29), (30, 31, 32), (33, 34), (35, 36), (37,), (38,), None, None, (39,), None, None, None, None, None, None, None, (40,), (41,), None, None, None, None, None, None, None, (43, 44, 45), (46, 47), (48, 49, 50), (51, 52), (53, 54, 55), (56, 57), (58, 59), (60, 61), (62, 63), (64, 65), (66,), (67,), (68,), None, (69,), (70,), None, (5, 6, 7, 8), (9, 10, 11, 12), (13, 14, 15, 16), (17, 18, 19, 20), (21, 22, 23, 24), (25,), None, None, None, None, (37,), (38,), None, (39,), None, None, None, (40,), None, None, None, (42,), None, None, (0, 1, 2, 3, 4), (26, 27), (0, 1, 2, 3, 4), (26, 27)]
	v = [0] * 71
	for _ in range(10, 1 + hi):
		for i in range(71):
			v[i] = 0
		for i in range(71):
			if not t[i]:
				continue
			c = u[i]
			for j in t[i]:
				v[j] = (v[j] + c) % mod
		(u, v) = (v, u)
		ans.append(sum(u) % mod)
	return ans
q = int(input())
ns = [int(input()) for _ in range(q)]
ans = solve(max(ns))
print(*(ans[n] for n in ns), sep='\n')


import os
import sys
from collections import defaultdict
MOD = 1000000007
primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97}
is_prime = [i in primes or i >= 64 for i in range(128)]
mult = 1 + 128 * (1 + 128 * (1 + 128 * (1 + 128)))
mat_col_memo = {}

def mat_col(t, start_digit=0):
	retv = mat_col_memo.get((t, start_digit))
	if not retv is None:
		return retv
	retv = {}
	for d in range(start_digit, 10):
		newt = t // 128 + d * mult
		if is_prime[newt % 128] and is_prime[newt // 128 % 128] and is_prime[newt // (128 * 128) % 128]:
			retv[newt] = 1
	mat_col_memo[t, start_digit] = retv
	return retv

def matf_to_vec(mat, vec):
	retv = defaultdict(lambda : 0, {})
	for (j, v) in vec.items():
		for (i, v2) in mat(j).items():
			retv[i] = (retv[i] + v * v2) % MOD
	return retv

def mat_to_vec(mat, vec):
	retv = defaultdict(lambda : 0, {})
	for (j, v) in vec.items():
		for (i, v2) in mat[j].items():
			retv[i] = (retv[i] + v * v2) % MOD
	return retv

def mat_to_straight_vec(mat, vec, out):
	for i in range(len(out)):
		out[i] = 0
	for (j, mj) in mat.items():
		v = vec[j]
		for (i, v2) in mj.items():
			out[i] += v * v2
	for i in range(len(out)):
		out[i] %= MOD

def mat_prod(mat1, mat2):
	retv = defaultdict(lambda : defaultdict(lambda : 0, {}))
	for (k, m2_k) in mat2.items():
		for (j, m1_j) in mat1.items():
			for (i, v) in m1_j.items():
				v2 = m2_k.get(j)
				if not v2 is None:
					retv[k][i] = (retv[k][i] + v * m2_k[j]) % MOD
	return retv
nums = [{64 * mult: 1}]
i = 0
while True:
	start_digit = 1 if i == 0 else 0
	i += 1
	nums.append(matf_to_vec(lambda d: mat_col(d, start_digit), nums[-1]))
	if i >= 32:
		break
mat = {k: mat_col(k, 0) for k in nums[-1].keys()}
assert all((all((k2 in mat for k2 in mat[k].keys())) for k in mat.keys()))
last_vec = nums[-1]
keys = list(last_vec.keys())
size = len(keys)
k2i = {keys[i]: i for i in range(size)}
straight_vec = [0 for _ in range(size)]
for (k, v) in last_vec.items():
	straight_vec[k2i[k]] = v
straight_mat = defaultdict(lambda : defaultdict(lambda : 0, {}))
for (i, mi) in mat.items():
	for (j, v) in mi.items():
		if v > 0:
			straight_mat[k2i[i]][k2i[j]] = v
mat_powers = {1: straight_mat}

def mpow(n):
	retv = mat_powers.get(n)
	if not retv is None:
		return retv
	if n & n - 1 == 0:
		mh = mpow(n // 2)
		retv = mat_powers[n] = mat_prod(mh, mh)
	else:
		a = n & n - 1
		b = n - a
		retv = mat_powers[n] = mat_prod(mpow(a), mpow(b))
	return retv
q = int(input())
(v1, v2) = (straight_vec.copy(), straight_vec.copy())
pows = sorted([(int(input()), i) for i in range(q)])
results = []
lastp = len(nums) - 1
(v1, v2) = (straight_vec.copy(), straight_vec.copy())
for (p, i) in pows:
	if p < len(nums):
		results.append((sum(nums[p].values()) % MOD, i))
		continue
	pw = p - lastp
	lastp = p
	pw2 = 15
	while pw > 0:
		if pw & pw2:
			mat_to_straight_vec(mpow(pw & pw2), v1, v2)
			(v1, v2) = (v2, v1)
		pw -= pw & pw2
		pw2 *= 16
	results.append((sum(v1) % MOD, i))
for (p, i) in sorted(results, key=lambda kw: kw[1]):
	print(p)


mod = 10 ** 9 + 7
A = [0, 0, 0, 0, 0, 2, 3, 15, 2, 0]
B = [0, 0, 0, 0, 0, 4, 9, 13, 17, 2]
results = [1, 9, 90, 303, 280, 218, 95, 101, 295]
for _ in range(int(input())):
	n = int(input())
	for i in range(len(A), n):
		A.append(2 * (A[i - 5] + B[i - 5]) % mod)
		B.append((A[i - 1] + A[i - 5] + 2 * B[i - 5]) % mod)
	print(results[n] if n < 9 else (5 * A[n - 1] + 9 * A[n - 2] + 19 * A[n - 3] + 6 * A[n - 4] + 3 * A[n - 5] + 2 * B[n - 1] + 5 * B[n - 2] + 20 * B[n - 3] + 5 * B[n - 4] + 4 * B[n - 5]) % mod)


mod = 10 ** 9 + 7
A = [0, 0, 0, 0, 0, 2, 3, 15, 2, 0]
B = [0, 0, 0, 0, 0, 4, 9, 13, 17, 2]
results = [1, 9, 90, 303, 280, 218, 95, 101, 295]
for _ in range(int(input())):
	n = int(input())
	for i in range(len(A), n):
		A.append(2 * (A[i - 5] + B[i - 5]) % mod)
		B.append((A[i - 1] + A[i - 5] + 2 * B[i - 5]) % mod)
	print(results[n] if n < 9 else (5 * A[n - 1] + 9 * A[n - 2] + 19 * A[n - 3] + 6 * A[n - 4] + 3 * A[n - 5] + 2 * B[n - 1] + 5 * B[n - 2] + 20 * B[n - 3] + 5 * B[n - 4] + 4 * B[n - 5]) % mod)


mod = 10 ** 9 + 7
A = [0, 0, 0, 0, 0, 2, 3, 15, 2, 0]
B = [0, 0, 0, 0, 0, 4, 9, 13, 17, 2]
results = [1, 9, 90, 303, 280, 218, 95, 101, 295]
for _ in range(int(input())):
	n = int(input())
	for i in range(len(A), n):
		A.append(2 * (A[i - 5] + B[i - 5]) % mod)
		B.append((A[i - 1] + A[i - 5] + 2 * B[i - 5]) % mod)
	print(results[n] if n < 9 else (5 * A[n - 1] + 9 * A[n - 2] + 19 * A[n - 3] + 6 * A[n - 4] + 3 * A[n - 5] + 2 * B[n - 1] + 5 * B[n - 2] + 20 * B[n - 3] + 5 * B[n - 4] + 4 * B[n - 5]) % mod)


def solve(hi):
	mod = 7 + 10 ** 9
	ans = [0, 9, 90, 303, 280, 218, 95, 101, 295, 513]
	u = [2, 2, 2, 2, 2, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 2, 17, 17, 15, 15, 15, 15, 15, 15, 15, 15, 15, 6, 6, 6, 6, 4, 2, 13, 13, 13, 13, 13, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 0, 0, 0, 0]
	t = [(26, 27), (28, 29), (30, 31, 32), (33, 34), (35, 36), (37,), (38,), None, None, (39,), None, None, None, None, None, None, None, (40,), (41,), None, None, None, None, None, None, None, (43, 44, 45), (46, 47), (48, 49, 50), (51, 52), (53, 54, 55), (56, 57), (58, 59), (60, 61), (62, 63), (64, 65), (66,), (67,), (68,), None, (69,), (70,), None, (5, 6, 7, 8), (9, 10, 11, 12), (13, 14, 15, 16), (17, 18, 19, 20), (21, 22, 23, 24), (25,), None, None, None, None, (37,), (38,), None, (39,), None, None, None, (40,), None, None, None, (42,), None, None, (0, 1, 2, 3, 4), (26, 27), (0, 1, 2, 3, 4), (26, 27)]
	v = [0] * 71
	for _ in range(10, 1 + hi):
		for i in range(71):
			v[i] = 0
		for i in range(71):
			if not t[i]:
				continue
			c = u[i]
			for j in t[i]:
				v[j] = (v[j] + c) % mod
		(u, v) = (v, u)
		ans.append(sum(u) % mod)
	return ans
q = int(input())
ns = [int(input()) for _ in range(q)]
ans = solve(max(ns))
print(*(ans[n] for n in ns), sep='\n')


import sys
primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43}

def canextend(l, s):
	(s, l) = (s + l % 10, l // 10)
	(s, l) = (s + l % 10, l // 10)
	if not s in primes:
		return False
	(s, l) = (s + l % 10, l // 10)
	if not s in primes:
		return False
	(s, l) = (s + l % 10, l // 10)
	if not s in primes:
		return False
	return True
last4digitmap = []
for i in range(10000):
	followups = []
	for j in range(10):
		if canextend(i, j):
			followups.append(i % 1000 * 10 + j)
	last4digitmap.append(followups)

def extend1(resultsofar):
	result = {}
	for (k, v) in resultsofar.items():
		for n in last4digitmap[k]:
			result[n] = result.setdefault(n, 0) + v
	return result

def good4(x):
	(a, x) = (x % 10, x // 10)
	(b, x) = (x % 10, x // 10)
	(c, x) = (x % 10, x // 10)
	d = x
	return a + b + c + d in primes and a + b + c in primes and (b + c + d in primes)
l = {x: 1 for x in range(1000, 10000) if good4(x)}
q = int(input().strip())
queries = []
for a0 in range(q):
	n = int(input().strip())
	queries.append(n)
todo = sorted(queries)
while todo[0] < 5:
	todo.pop(0)
cache = [0] * 400001
cache[1] = len(range(1, 10))
cache[2] = len(range(10, 100))
cache[3] = len([i for i in range(100, 1000) if sum([int(x) for x in str(i)]) in primes])
cache[4] = len([i for i in range(1000, 10000) if sum([int(x) for x in str(i)]) in primes and sum([int(x) for x in str(i)[:3]]) in primes and (sum([int(x) for x in str(i)[-3:]]) in primes)])
lastlength = 4
l = {x: 1 for x in range(1000, 10000) if good4(x)}
for stringlength in todo:
	stepstodo = stringlength - lastlength
	while stepstodo >= 1:
		l = extend1(l)
		stepstodo -= 1
	s = 0
	for (k, v) in l.items():
		l[k] = v % 1000000007
		s += v
	cache[stringlength] = s % 1000000007
	lastlength = stringlength
for n in queries:
	print(cache[n])


import sys
primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43}

def canextend(l, s):
	(s, l) = (s + l % 10, l // 10)
	(s, l) = (s + l % 10, l // 10)
	if not s in primes:
		return False
	(s, l) = (s + l % 10, l // 10)
	if not s in primes:
		return False
	(s, l) = (s + l % 10, l // 10)
	if not s in primes:
		return False
	return True
last4digitmap = []
for i in range(10000):
	followups = []
	for j in range(10):
		if canextend(i, j):
			followups.append(i % 1000 * 10 + j)
	last4digitmap.append(followups)

def extend1(resultsofar):
	result = {}
	for (k, v) in resultsofar.items():
		for n in last4digitmap[k]:
			result[n] = result.setdefault(n, 0) + v
	return result

def good4(x):
	(a, x) = (x % 10, x // 10)
	(b, x) = (x % 10, x // 10)
	(c, x) = (x % 10, x // 10)
	d = x
	return a + b + c + d in primes and a + b + c in primes and (b + c + d in primes)
l = {x: 1 for x in range(1000, 10000) if good4(x)}
q = int(input().strip())
queries = []
for a0 in range(q):
	n = int(input().strip())
	queries.append(n)
todo = sorted(queries)
while todo[0] < 5:
	todo.pop(0)
cache = [0] * 400001
cache[1] = len(range(1, 10))
cache[2] = len(range(10, 100))
cache[3] = len([i for i in range(100, 1000) if sum([int(x) for x in str(i)]) in primes])
cache[4] = len([i for i in range(1000, 10000) if sum([int(x) for x in str(i)]) in primes and sum([int(x) for x in str(i)[:3]]) in primes and (sum([int(x) for x in str(i)[-3:]]) in primes)])
lastlength = 4
l = {x: 1 for x in range(1000, 10000) if good4(x)}
for stringlength in todo:
	stepstodo = stringlength - lastlength
	while stepstodo >= 1:
		l = extend1(l)
		stepstodo -= 1
	s = 0
	for (k, v) in l.items():
		l[k] = v % 1000000007
		s += v
	cache[stringlength] = s % 1000000007
	lastlength = stringlength
for n in queries:
	print(cache[n])


mod = 10 ** 9 + 7
A = [0, 0, 0, 0, 0, 2, 3, 15, 2, 0]
B = [0, 0, 0, 0, 0, 4, 9, 13, 17, 2]
results = [1, 9, 90, 303, 280, 218, 95, 101, 295]
for _ in range(int(input())):
	n = int(input())
	for i in range(len(A), n):
		A.append(2 * (A[i - 5] + B[i - 5]) % mod)
		B.append((A[i - 1] + A[i - 5] + 2 * B[i - 5]) % mod)
	print(results[n] if n < 9 else (5 * A[n - 1] + 9 * A[n - 2] + 19 * A[n - 3] + 6 * A[n - 4] + 3 * A[n - 5] + 2 * B[n - 1] + 5 * B[n - 2] + 20 * B[n - 3] + 5 * B[n - 4] + 4 * B[n - 5]) % mod)


mod = 10 ** 9 + 7
A = [0, 0, 0, 0, 0, 2, 3, 15, 2, 0]
B = [0, 0, 0, 0, 0, 4, 9, 13, 17, 2]
results = [1, 9, 90, 303, 280, 218, 95, 101, 295]
for _ in range(int(input())):
	n = int(input())
	for i in range(len(A), n):
		A.append(2 * (A[i - 5] + B[i - 5]) % mod)
		B.append((A[i - 1] + A[i - 5] + 2 * B[i - 5]) % mod)
	print(results[n] if n < 9 else (5 * A[n - 1] + 9 * A[n - 2] + 19 * A[n - 3] + 6 * A[n - 4] + 3 * A[n - 5] + 2 * B[n - 1] + 5 * B[n - 2] + 20 * B[n - 3] + 5 * B[n - 4] + 4 * B[n - 5]) % mod)


mod = 10 ** 9 + 7
A = [0, 0, 0, 0, 0, 2, 3, 15, 2, 0]
B = [0, 0, 0, 0, 0, 4, 9, 13, 17, 2]
results = [1, 9, 90, 303, 280, 218, 95, 101, 295]
for _ in range(int(input())):
	n = int(input())
	for i in range(len(A), n):
		A.append(2 * (A[i - 5] + B[i - 5]) % mod)
		B.append((A[i - 1] + A[i - 5] + 2 * B[i - 5]) % mod)
	print(results[n] if n < 9 else (5 * A[n - 1] + 9 * A[n - 2] + 19 * A[n - 3] + 6 * A[n - 4] + 3 * A[n - 5] + 2 * B[n - 1] + 5 * B[n - 2] + 20 * B[n - 3] + 5 * B[n - 4] + 4 * B[n - 5]) % mod)


mod = 10 ** 9 + 7
A = [0, 0, 0, 0, 0, 2, 3, 15, 2, 0]
B = [0, 0, 0, 0, 0, 4, 9, 13, 17, 2]
results = [1, 9, 90, 303, 280, 218, 95, 101, 295]
for _ in range(int(input())):
	n = int(input())
	for i in range(len(A), n):
		A.append(2 * (A[i - 5] + B[i - 5]) % mod)
		B.append((A[i - 1] + A[i - 5] + 2 * B[i - 5]) % mod)
	print(results[n] if n < 9 else (5 * A[n - 1] + 9 * A[n - 2] + 19 * A[n - 3] + 6 * A[n - 4] + 3 * A[n - 5] + 2 * B[n - 1] + 5 * B[n - 2] + 20 * B[n - 3] + 5 * B[n - 4] + 4 * B[n - 5]) % mod)


mod = 10 ** 9 + 7
A = [0, 0, 0, 0, 0, 2, 3, 15, 2, 0]
B = [0, 0, 0, 0, 0, 4, 9, 13, 17, 2]
results = [1, 9, 90, 303, 280, 218, 95, 101, 295]
for _ in range(int(input())):
	n = int(input())
	for i in range(len(A), n):
		A.append(2 * (A[i - 5] + B[i - 5]) % mod)
		B.append((A[i - 1] + A[i - 5] + 2 * B[i - 5]) % mod)
	print(results[n] if n < 9 else (5 * A[n - 1] + 9 * A[n - 2] + 19 * A[n - 3] + 6 * A[n - 4] + 3 * A[n - 5] + 2 * B[n - 1] + 5 * B[n - 2] + 20 * B[n - 3] + 5 * B[n - 4] + 4 * B[n - 5]) % mod)


mod = 10 ** 9 + 7
A = [0, 0, 0, 0, 0, 2, 3, 15, 2, 0]
B = [0, 0, 0, 0, 0, 4, 9, 13, 17, 2]
results = [1, 9, 90, 303, 280, 218, 95, 101, 295]
for _ in range(int(input())):
	n = int(input())
	for i in range(len(A), n):
		A.append(2 * (A[i - 5] + B[i - 5]) % mod)
		B.append((A[i - 1] + A[i - 5] + 2 * B[i - 5]) % mod)
	print(results[n] if n < 9 else (5 * A[n - 1] + 9 * A[n - 2] + 19 * A[n - 3] + 6 * A[n - 4] + 3 * A[n - 5] + 2 * B[n - 1] + 5 * B[n - 2] + 20 * B[n - 3] + 5 * B[n - 4] + 4 * B[n - 5]) % mod)


mod = 10 ** 9 + 7
A = [0, 0, 0, 0, 0, 2, 3, 15, 2, 0]
B = [0, 0, 0, 0, 0, 4, 9, 13, 17, 2]
results = [1, 9, 90, 303, 280, 218, 95, 101, 295]
for _ in range(int(input())):
	n = int(input())
	for i in range(len(A), n):
		A.append(2 * (A[i - 5] + B[i - 5]) % mod)
		B.append((A[i - 1] + A[i - 5] + 2 * B[i - 5]) % mod)
	print(results[n] if n < 9 else (5 * A[n - 1] + 9 * A[n - 2] + 19 * A[n - 3] + 6 * A[n - 4] + 3 * A[n - 5] + 2 * B[n - 1] + 5 * B[n - 2] + 20 * B[n - 3] + 5 * B[n - 4] + 4 * B[n - 5]) % mod)


mod = 10 ** 9 + 7
A = [0, 0, 0, 0, 0, 2, 3, 15, 2, 0]
B = [0, 0, 0, 0, 0, 4, 9, 13, 17, 2]
results = [1, 9, 90, 303, 280, 218, 95, 101, 295]
for _ in range(int(input())):
	n = int(input())
	for i in range(len(A), n):
		A.append(2 * (A[i - 5] + B[i - 5]) % mod)
		B.append((A[i - 1] + A[i - 5] + 2 * B[i - 5]) % mod)
	print(results[n] if n < 9 else (5 * A[n - 1] + 9 * A[n - 2] + 19 * A[n - 3] + 6 * A[n - 4] + 3 * A[n - 5] + 2 * B[n - 1] + 5 * B[n - 2] + 20 * B[n - 3] + 5 * B[n - 4] + 4 * B[n - 5]) % mod)


mod = 10 ** 9 + 7
A = [0, 0, 0, 0, 0, 2, 3, 15, 2, 0]
B = [0, 0, 0, 0, 0, 4, 9, 13, 17, 2]
results = [1, 9, 90, 303, 280, 218, 95, 101, 295]
for _ in range(int(input())):
	n = int(input())
	for i in range(len(A), n):
		A.append(2 * (A[i - 5] + B[i - 5]) % mod)
		B.append((A[i - 1] + A[i - 5] + 2 * B[i - 5]) % mod)
	print(results[n] if n < 9 else (5 * A[n - 1] + 9 * A[n - 2] + 19 * A[n - 3] + 6 * A[n - 4] + 3 * A[n - 5] + 2 * B[n - 1] + 5 * B[n - 2] + 20 * B[n - 3] + 5 * B[n - 4] + 4 * B[n - 5]) % mod)


import math
import os
import random
import re
import sys
mod = 10 ** 9 + 7
A = [0, 0, 0, 0, 0, 2, 3, 15, 2, 0]
B = [0, 0, 0, 0, 0, 4, 9, 13, 17, 2]
results = [1, 9, 90, 303, 280, 218, 95, 101, 295]
for _ in range(int(input())):
	n = int(input())
	for i in range(len(A), n):
		A.append(2 * (A[i - 5] + B[i - 5]) % mod)
		B.append((A[i - 1] + A[i - 5] + 2 * B[i - 5]) % mod)
	print(results[n] if n < 9 else (5 * A[n - 1] + 9 * A[n - 2] + 19 * A[n - 3] + 6 * A[n - 4] + 3 * A[n - 5] + 2 * B[n - 1] + 5 * B[n - 2] + 20 * B[n - 3] + 5 * B[n - 4] + 4 * B[n - 5]) % mod)


import math
import os
import random
import re
import sys
mod = 10 ** 9 + 7
A = [0, 0, 0, 0, 0, 2, 3, 15, 2, 0]
B = [0, 0, 0, 0, 0, 4, 9, 13, 17, 2]
results = [1, 9, 90, 303, 280, 218, 95, 101, 295]
for _ in range(int(input())):
	n = int(input())
	for i in range(len(A), n):
		A.append(2 * (A[i - 5] + B[i - 5]) % mod)
		B.append((A[i - 1] + A[i - 5] + 2 * B[i - 5]) % mod)
	print(results[n] if n < 9 else (5 * A[n - 1] + 9 * A[n - 2] + 19 * A[n - 3] + 6 * A[n - 4] + 3 * A[n - 5] + 2 * B[n - 1] + 5 * B[n - 2] + 20 * B[n - 3] + 5 * B[n - 4] + 4 * B[n - 5]) % mod)


mod = 10 ** 9 + 7
A = [0, 0, 0, 0, 0, 2, 3, 15, 2, 0]
B = [0, 0, 0, 0, 0, 4, 9, 13, 17, 2]
results = [1, 9, 90, 303, 280, 218, 95, 101, 295]
for _ in range(int(input())):
	n = int(input())
	for i in range(len(A), n):
		A.append(2 * (A[i - 5] + B[i - 5]) % mod)
		B.append((A[i - 1] + A[i - 5] + 2 * B[i - 5]) % mod)
	print(results[n] if n < 9 else (5 * A[n - 1] + 9 * A[n - 2] + 19 * A[n - 3] + 6 * A[n - 4] + 3 * A[n - 5] + 2 * B[n - 1] + 5 * B[n - 2] + 20 * B[n - 3] + 5 * B[n - 4] + 4 * B[n - 5]) % mod)


mod = 10 ** 9 + 7
A = [0, 0, 0, 0, 0, 2, 3, 15, 2, 0]
B = [0, 0, 0, 0, 0, 4, 9, 13, 17, 2]
results = [1, 9, 90, 303, 280, 218, 95, 101, 295]
for _ in range(int(input())):
	n = int(input())
	for i in range(len(A), n):
		A.append(2 * (A[i - 5] + B[i - 5]) % mod)
		B.append((A[i - 1] + A[i - 5] + 2 * B[i - 5]) % mod)
	print(results[n] if n < 9 else (5 * A[n - 1] + 9 * A[n - 2] + 19 * A[n - 3] + 6 * A[n - 4] + 3 * A[n - 5] + 2 * B[n - 1] + 5 * B[n - 2] + 20 * B[n - 3] + 5 * B[n - 4] + 4 * B[n - 5]) % mod)


import math
import os
import random
import re
import sys
mod = 10 ** 9 + 7
A = [0, 0, 0, 0, 0, 2, 3, 15, 2, 0]
B = [0, 0, 0, 0, 0, 4, 9, 13, 17, 2]
results = [1, 9, 90, 303, 280, 218, 95, 101, 295]
for _ in range(int(input())):
	n = int(input())
	for i in range(len(A), n):
		A.append(2 * (A[i - 5] + B[i - 5]) % mod)
		B.append((A[i - 1] + A[i - 5] + 2 * B[i - 5]) % mod)
	print(results[n] if n < 9 else (5 * A[n - 1] + 9 * A[n - 2] + 19 * A[n - 3] + 6 * A[n - 4] + 3 * A[n - 5] + 2 * B[n - 1] + 5 * B[n - 2] + 20 * B[n - 3] + 5 * B[n - 4] + 4 * B[n - 5]) % mod)


mod = 10 ** 9 + 7
A = [0, 0, 0, 0, 0, 2, 3, 15, 2, 0]
B = [0, 0, 0, 0, 0, 4, 9, 13, 17, 2]
results = [1, 9, 90, 303, 280, 218, 95, 101, 295]
for _ in range(int(input())):
	n = int(input())
	for i in range(len(A), n):
		A.append(2 * (A[i - 5] + B[i - 5]) % mod)
		B.append((A[i - 1] + A[i - 5] + 2 * B[i - 5]) % mod)
	print(results[n] if n < 9 else (5 * A[n - 1] + 9 * A[n - 2] + 19 * A[n - 3] + 6 * A[n - 4] + 3 * A[n - 5] + 2 * B[n - 1] + 5 * B[n - 2] + 20 * B[n - 3] + 5 * B[n - 4] + 4 * B[n - 5]) % mod)


mod = 10 ** 9 + 7
A = [0, 0, 0, 0, 0, 2, 3, 15, 2, 0]
B = [0, 0, 0, 0, 0, 4, 9, 13, 17, 2]
results = [1, 9, 90, 303, 280, 218, 95, 101, 295]
for _ in range(int(input())):
	n = int(input())
	for i in range(len(A), n):
		A.append(2 * (A[i - 5] + B[i - 5]) % mod)
		B.append((A[i - 1] + A[i - 5] + 2 * B[i - 5]) % mod)
	print(results[n] if n < 9 else (5 * A[n - 1] + 9 * A[n - 2] + 19 * A[n - 3] + 6 * A[n - 4] + 3 * A[n - 5] + 2 * B[n - 1] + 5 * B[n - 2] + 20 * B[n - 3] + 5 * B[n - 4] + 4 * B[n - 5]) % mod)


mod = 10 ** 9 + 7
A = [0, 0, 0, 0, 0, 2, 3, 15, 2, 0]
B = [0, 0, 0, 0, 0, 4, 9, 13, 17, 2]
results = [1, 9, 90, 303, 280, 218, 95, 101, 295]
for _ in range(int(input())):
	n = int(input())
	for i in range(len(A), n):
		A.append(2 * (A[i - 5] + B[i - 5]) % mod)
		B.append((A[i - 1] + A[i - 5] + 2 * B[i - 5]) % mod)
	print(results[n] if n < 9 else (5 * A[n - 1] + 9 * A[n - 2] + 19 * A[n - 3] + 6 * A[n - 4] + 3 * A[n - 5] + 2 * B[n - 1] + 5 * B[n - 2] + 20 * B[n - 3] + 5 * B[n - 4] + 4 * B[n - 5]) % mod)


import math
import os
import random
import re
import sys
mod = 10 ** 9 + 7
suf_gen = [[], [], [12, 19], [21, 38], [], [9], [], [], [5], [21, 38], [], [24, 27], [29], [], [], [57, 69], [5], [], [48, 6, 59, 41], [], [50, 37], [55, 18, 45], [], [61, 8, 56], [47, 66], [63], [], [10, 33], [22], [], [], [], [], [], [46], [30, 26], [49, 25, 60, 13], [], [36, 62], [], [], [], [52], [], [34], [17, 14, 7, 53], [3, 64, 65, 11, 15], [42], [29], [42], [], [70, 4, 0], [3, 64, 65, 11, 15], [], [], [44, 16, 32, 39], [], [28, 67], [21, 38], [], [], [34], [31, 43, 68, 1], [58], [51, 20], [23, 2, 35], [], [], [], [40], [54]]

def primeDigitSums(T):
	ans = [0] * max(T + 1, 9)
	ans[:9] = [0, 9, 90, 303, 280, 218, 95, 101, 295]
	suf_v = [2, 4, 3, 15, 2, 0, 4, 4, 2, 1, 2, 15, 2, 4, 4, 15, 4, 4, 9, 2, 3, 13, 0, 3, 3, 4, 2, 3, 2, 0, 2, 4, 4, 2, 0, 3, 9, 2, 13, 4, 2, 4, 0, 4, 4, 9, 1, 2, 4, 4, 2, 3, 1, 4, 0, 9, 2, 3, 1, 4, 4, 2, 9, 0, 15, 15, 2, 2, 4, 3, 2]
	for i in range(9, T + 1):
		new_suf_v = [0] * 71
		for j in range(71):
			for k in suf_gen[j]:
				new_suf_v[k] = (new_suf_v[k] + suf_v[j]) % mod
		suf_v = new_suf_v
		ans[i] = sum(suf_v) % mod
	return ans
q = int(input().strip())
n = [0] * q
for q_itr in range(q):
	n[q_itr] = int(input().strip())
result = primeDigitSums(max(n))
ans = ''
for i in n:
	ans += str(result[i]) + '\n'
print(ans)


mod = 10 ** 9 + 7
A = [0, 0, 0, 0, 0, 2, 3, 15, 2, 0]
B = [0, 0, 0, 0, 0, 4, 9, 13, 17, 2]
results = [1, 9, 90, 303, 280, 218, 95, 101, 295]
for _ in range(int(input())):
	n = int(input())
	for i in range(len(A), n):
		A.append(2 * (A[i - 5] + B[i - 5]) % mod)
		B.append((A[i - 1] + A[i - 5] + 2 * B[i - 5]) % mod)
	print(results[n] if n < 9 else (5 * A[n - 1] + 9 * A[n - 2] + 19 * A[n - 3] + 6 * A[n - 4] + 3 * A[n - 5] + 2 * B[n - 1] + 5 * B[n - 2] + 20 * B[n - 3] + 5 * B[n - 4] + 4 * B[n - 5]) % mod)


mod = 10 ** 9 + 7
A = [0, 0, 0, 0, 0, 2, 3, 15, 2, 0]
B = [0, 0, 0, 0, 0, 4, 9, 13, 17, 2]
output = [1, 9, 90, 303, 280, 218, 95, 101, 295]
for _ in range(int(input())):
	n = int(input())
	for i in range(len(A), n):
		A.append(2 * (A[i - 5] + B[i - 5]) % mod)
		B.append((A[i - 1] + A[i - 5] + 2 * B[i - 5]) % mod)
	print(output[n] if n < 9 else (5 * A[n - 1] + 9 * A[n - 2] + 19 * A[n - 3] + 6 * A[n - 4] + 3 * A[n - 5] + 2 * B[n - 1] + 5 * B[n - 2] + 20 * B[n - 3] + 5 * B[n - 4] + 4 * B[n - 5]) % mod)


mod = 10 ** 9 + 7
A = [0, 0, 0, 0, 0, 2, 3, 15, 2, 0]
B = [0, 0, 0, 0, 0, 4, 9, 13, 17, 2]
results = [1, 9, 90, 303, 280, 218, 95, 101, 295]
for _ in range(int(input())):
	n = int(input())
	for i in range(len(A), n):
		A.append(2 * (A[i - 5] + B[i - 5]) % mod)
		B.append((A[i - 1] + A[i - 5] + 2 * B[i - 5]) % mod)
	print(results[n] if n < 9 else (5 * A[n - 1] + 9 * A[n - 2] + 19 * A[n - 3] + 6 * A[n - 4] + 3 * A[n - 5] + 2 * B[n - 1] + 5 * B[n - 2] + 20 * B[n - 3] + 5 * B[n - 4] + 4 * B[n - 5]) % mod)


mod = 10 ** 9 + 7
A = [0, 0, 0, 0, 0, 2, 3, 15, 2, 0]
B = [0, 0, 0, 0, 0, 4, 9, 13, 17, 2]
results = [1, 9, 90, 303, 280, 218, 95, 101, 295]
for _ in range(int(input())):
	n = int(input())
	for i in range(len(A), n):
		A.append(2 * (A[i - 5] + B[i - 5]) % mod)
		B.append((A[i - 1] + A[i - 5] + 2 * B[i - 5]) % mod)
	print(results[n] if n < 9 else (5 * A[n - 1] + 9 * A[n - 2] + 19 * A[n - 3] + 6 * A[n - 4] + 3 * A[n - 5] + 2 * B[n - 1] + 5 * B[n - 2] + 20 * B[n - 3] + 5 * B[n - 4] + 4 * B[n - 5]) % mod)


mod = 10 ** 9 + 7
A = [0, 0, 0, 0, 0, 2, 3, 15, 2, 0]
B = [0, 0, 0, 0, 0, 4, 9, 13, 17, 2]
results = [1, 9, 90, 303, 280, 218, 95, 101, 295]
for _ in range(int(input())):
	n = int(input())
	for i in range(len(A), n):
		A.append(2 * (A[i - 5] + B[i - 5]) % mod)
		B.append((A[i - 1] + A[i - 5] + 2 * B[i - 5]) % mod)
	print(results[n] if n < 9 else (5 * A[n - 1] + 9 * A[n - 2] + 19 * A[n - 3] + 6 * A[n - 4] + 3 * A[n - 5] + 2 * B[n - 1] + 5 * B[n - 2] + 20 * B[n - 3] + 5 * B[n - 4] + 4 * B[n - 5]) % mod)


mod = 10 ** 9 + 7
A = [0, 0, 0, 0, 0, 2, 3, 15, 2, 0]
B = [0, 0, 0, 0, 0, 4, 9, 13, 17, 2]
results = [1, 9, 90, 303, 280, 218, 95, 101, 295]
for _ in range(int(input())):
	n = int(input())
	for i in range(len(A), n):
		A.append(2 * (A[i - 5] + B[i - 5]) % mod)
		B.append((A[i - 1] + A[i - 5] + 2 * B[i - 5]) % mod)
	print(results[n] if n < 9 else (5 * A[n - 1] + 9 * A[n - 2] + 19 * A[n - 3] + 6 * A[n - 4] + 3 * A[n - 5] + 2 * B[n - 1] + 5 * B[n - 2] + 20 * B[n - 3] + 5 * B[n - 4] + 4 * B[n - 5]) % mod)


mod = 10 ** 9 + 7
A = [0, 0, 0, 0, 0, 2, 3, 15, 2, 0]
B = [0, 0, 0, 0, 0, 4, 9, 13, 17, 2]
results = [1, 9, 90, 303, 280, 218, 95, 101, 295]
for _ in range(int(input())):
	n = int(input())
	for i in range(len(A), n):
		A.append(2 * (A[i - 5] + B[i - 5]) % mod)
		B.append((A[i - 1] + A[i - 5] + 2 * B[i - 5]) % mod)
	print(results[n] if n < 9 else (5 * A[n - 1] + 9 * A[n - 2] + 19 * A[n - 3] + 6 * A[n - 4] + 3 * A[n - 5] + 2 * B[n - 1] + 5 * B[n - 2] + 20 * B[n - 3] + 5 * B[n - 4] + 4 * B[n - 5]) % mod)


mod = 10 ** 9 + 7
A = [0, 0, 0, 0, 0, 2, 3, 15, 2, 0]
B = [0, 0, 0, 0, 0, 4, 9, 13, 17, 2]
results = [1, 9, 90, 303, 280, 218, 95, 101, 295]
for _ in range(int(input())):
	n = int(input())
	for i in range(len(A), n):
		A.append(2 * (A[i - 5] + B[i - 5]) % mod)
		B.append((A[i - 1] + A[i - 5] + 2 * B[i - 5]) % mod)
	print(results[n] if n < 9 else (5 * A[n - 1] + 9 * A[n - 2] + 19 * A[n - 3] + 6 * A[n - 4] + 3 * A[n - 5] + 2 * B[n - 1] + 5 * B[n - 2] + 20 * B[n - 3] + 5 * B[n - 4] + 4 * B[n - 5]) % mod)


mod = 10 ** 9 + 7
A = [0, 0, 0, 0, 0, 2, 3, 15, 2, 0]
B = [0, 0, 0, 0, 0, 4, 9, 13, 17, 2]
results = [1, 9, 90, 303, 280, 218, 95, 101, 295]
for _ in range(int(input())):
	n = int(input())
	for i in range(len(A), n):
		A.append(2 * (A[i - 5] + B[i - 5]) % mod)
		B.append((A[i - 1] + A[i - 5] + 2 * B[i - 5]) % mod)
	print(results[n] if n < 9 else (5 * A[n - 1] + 9 * A[n - 2] + 19 * A[n - 3] + 6 * A[n - 4] + 3 * A[n - 5] + 2 * B[n - 1] + 5 * B[n - 2] + 20 * B[n - 3] + 5 * B[n - 4] + 4 * B[n - 5]) % mod)


mod = 10 ** 9 + 7
A = [0, 0, 0, 0, 0, 2, 3, 15, 2, 0]
B = [0, 0, 0, 0, 0, 4, 9, 13, 17, 2]
results = [1, 9, 90, 303, 280, 218, 95, 101, 295]
for _ in range(int(input())):
	n = int(input())
	for i in range(len(A), n):
		A.append(2 * (A[i - 5] + B[i - 5]) % mod)
		B.append((A[i - 1] + A[i - 5] + 2 * B[i - 5]) % mod)
	print(results[n] if n < 9 else (5 * A[n - 1] + 9 * A[n - 2] + 19 * A[n - 3] + 6 * A[n - 4] + 3 * A[n - 5] + 2 * B[n - 1] + 5 * B[n - 2] + 20 * B[n - 3] + 5 * B[n - 4] + 4 * B[n - 5]) % mod)


mod = 10 ** 9 + 7
A = [0, 0, 0, 0, 0, 2, 3, 15, 2, 0]
B = [0, 0, 0, 0, 0, 4, 9, 13, 17, 2]
results = [1, 9, 90, 303, 280, 218, 95, 101, 295]
for _ in range(int(input())):
	n = int(input())
	for i in range(len(A), n):
		A.append(2 * (A[i - 5] + B[i - 5]) % mod)
		B.append((A[i - 1] + A[i - 5] + 2 * B[i - 5]) % mod)
	print(results[n] if n < 9 else (5 * A[n - 1] + 9 * A[n - 2] + 19 * A[n - 3] + 6 * A[n - 4] + 3 * A[n - 5] + 2 * B[n - 1] + 5 * B[n - 2] + 20 * B[n - 3] + 5 * B[n - 4] + 4 * B[n - 5]) % mod)


mod = 10 ** 9 + 7
A = [0, 0, 0, 0, 0, 2, 3, 15, 2, 0]
B = [0, 0, 0, 0, 0, 4, 9, 13, 17, 2]
results = [1, 9, 90, 303, 280, 218, 95, 101, 295]
for _ in range(int(input())):
	n = int(input())
	for i in range(len(A), n):
		A.append(2 * (A[i - 5] + B[i - 5]) % mod)
		B.append((A[i - 1] + A[i - 5] + 2 * B[i - 5]) % mod)
	print(results[n] if n < 9 else (5 * A[n - 1] + 9 * A[n - 2] + 19 * A[n - 3] + 6 * A[n - 4] + 3 * A[n - 5] + 2 * B[n - 1] + 5 * B[n - 2] + 20 * B[n - 3] + 5 * B[n - 4] + 4 * B[n - 5]) % mod)


mod = 10 ** 9 + 7
A = [0, 0, 0, 0, 0, 2, 3, 15, 2, 0]
B = [0, 0, 0, 0, 0, 4, 9, 13, 17, 2]
results = [1, 9, 90, 303, 280, 218, 95, 101, 295]
for _ in range(int(input())):
	n = int(input())
	for i in range(len(A), n):
		A.append(2 * (A[i - 5] + B[i - 5]) % mod)
		B.append((A[i - 1] + A[i - 5] + 2 * B[i - 5]) % mod)
	print(results[n] if n < 9 else (5 * A[n - 1] + 9 * A[n - 2] + 19 * A[n - 3] + 6 * A[n - 4] + 3 * A[n - 5] + 2 * B[n - 1] + 5 * B[n - 2] + 20 * B[n - 3] + 5 * B[n - 4] + 4 * B[n - 5]) % mod)


mod = 10 ** 9 + 7
A = [0, 0, 0, 0, 0, 2, 3, 15, 2, 0]
B = [0, 0, 0, 0, 0, 4, 9, 13, 17, 2]
results = [1, 9, 90, 303, 280, 218, 95, 101, 295]
for _ in range(int(input())):
	n = int(input())
	for i in range(len(A), n):
		A.append(2 * (A[i - 5] + B[i - 5]) % mod)
		B.append((A[i - 1] + A[i - 5] + 2 * B[i - 5]) % mod)
	print(results[n] if n < 9 else (5 * A[n - 1] + 9 * A[n - 2] + 19 * A[n - 3] + 6 * A[n - 4] + 3 * A[n - 5] + 2 * B[n - 1] + 5 * B[n - 2] + 20 * B[n - 3] + 5 * B[n - 4] + 4 * B[n - 5]) % mod)


mod = 10 ** 9 + 7
A = [0, 0, 0, 0, 0, 2, 3, 15, 2, 0]
B = [0, 0, 0, 0, 0, 4, 9, 13, 17, 2]
results = [1, 9, 90, 303, 280, 218, 95, 101, 295]
for _ in range(int(input())):
	n = int(input())
	for i in range(len(A), n):
		A.append(2 * (A[i - 5] + B[i - 5]) % mod)
		B.append((A[i - 1] + A[i - 5] + 2 * B[i - 5]) % mod)
	print(results[n] if n < 9 else (5 * A[n - 1] + 9 * A[n - 2] + 19 * A[n - 3] + 6 * A[n - 4] + 3 * A[n - 5] + 2 * B[n - 1] + 5 * B[n - 2] + 20 * B[n - 3] + 5 * B[n - 4] + 4 * B[n - 5]) % mod)


import math
import os
import random
import re
import sys
mod = 10 ** 9 + 7
A = [0, 0, 0, 0, 0, 2, 3, 15, 2, 0]
B = [0, 0, 0, 0, 0, 4, 9, 13, 17, 2]
results = [1, 9, 90, 303, 280, 218, 95, 101, 295]
for _ in range(int(input())):
	n = int(input())
	for i in range(len(A), n):
		A.append(2 * (A[i - 5] + B[i - 5]) % mod)
		B.append((A[i - 1] + A[i - 5] + 2 * B[i - 5]) % mod)
	print(results[n] if n < 9 else (5 * A[n - 1] + 9 * A[n - 2] + 19 * A[n - 3] + 6 * A[n - 4] + 3 * A[n - 5] + 2 * B[n - 1] + 5 * B[n - 2] + 20 * B[n - 3] + 5 * B[n - 4] + 4 * B[n - 5]) % mod)


mod = 10 ** 9 + 7
A = [0, 0, 0, 0, 0, 2, 3, 15, 2, 0]
B = [0, 0, 0, 0, 0, 4, 9, 13, 17, 2]
results = [1, 9, 90, 303, 280, 218, 95, 101, 295]
for _ in range(int(input())):
	n = int(input())
	for i in range(len(A), n):
		A.append(2 * (A[i - 5] + B[i - 5]) % mod)
		B.append((A[i - 1] + A[i - 5] + 2 * B[i - 5]) % mod)
	print(results[n] if n < 9 else (5 * A[n - 1] + 9 * A[n - 2] + 19 * A[n - 3] + 6 * A[n - 4] + 3 * A[n - 5] + 2 * B[n - 1] + 5 * B[n - 2] + 20 * B[n - 3] + 5 * B[n - 4] + 4 * B[n - 5]) % mod)


mod = 10 ** 9 + 7
A = [0, 0, 0, 0, 0, 2, 3, 15, 2, 0]
B = [0, 0, 0, 0, 0, 4, 9, 13, 17, 2]
results = [1, 9, 90, 303, 280, 218, 95, 101, 295]
for _ in range(int(input())):
	n = int(input())
	for i in range(len(A), n):
		A.append(2 * (A[i - 5] + B[i - 5]) % mod)
		B.append((A[i - 1] + A[i - 5] + 2 * B[i - 5]) % mod)
	print(results[n] if n < 9 else (5 * A[n - 1] + 9 * A[n - 2] + 19 * A[n - 3] + 6 * A[n - 4] + 3 * A[n - 5] + 2 * B[n - 1] + 5 * B[n - 2] + 20 * B[n - 3] + 5 * B[n - 4] + 4 * B[n - 5]) % mod)


mod = 10 ** 9 + 7
A = [0, 0, 0, 0, 0, 2, 3, 15, 2, 0]
B = [0, 0, 0, 0, 0, 4, 9, 13, 17, 2]
results = [1, 9, 90, 303, 280, 218, 95, 101, 295]
for _ in range(int(input())):
	n = int(input())
	for i in range(len(A), n):
		A.append(2 * (A[i - 5] + B[i - 5]) % mod)
		B.append((A[i - 1] + A[i - 5] + 2 * B[i - 5]) % mod)
	print(results[n] if n < 9 else (5 * A[n - 1] + 9 * A[n - 2] + 19 * A[n - 3] + 6 * A[n - 4] + 3 * A[n - 5] + 2 * B[n - 1] + 5 * B[n - 2] + 20 * B[n - 3] + 5 * B[n - 4] + 4 * B[n - 5]) % mod)


import math
import os
import random
import re
import sys
mod = 10 ** 9 + 7
A = [0, 0, 0, 0, 0, 2, 3, 15, 2, 0]
B = [0, 0, 0, 0, 0, 4, 9, 13, 17, 2]
results = [1, 9, 90, 303, 280, 218, 95, 101, 295]
for _ in range(int(input())):
	n = int(input())
	for i in range(len(A), n):
		A.append(2 * (A[i - 5] + B[i - 5]) % mod)
		B.append((A[i - 1] + A[i - 5] + 2 * B[i - 5]) % mod)
	print(results[n] if n < 9 else (5 * A[n - 1] + 9 * A[n - 2] + 19 * A[n - 3] + 6 * A[n - 4] + 3 * A[n - 5] + 2 * B[n - 1] + 5 * B[n - 2] + 20 * B[n - 3] + 5 * B[n - 4] + 4 * B[n - 5]) % mod)


mod = 10 ** 9 + 7
A = [0, 0, 0, 0, 0, 2, 3, 15, 2, 0]
B = [0, 0, 0, 0, 0, 4, 9, 13, 17, 2]
results = [1, 9, 90, 303, 280, 218, 95, 101, 295]
for _ in range(int(input())):
	n = int(input())
	for i in range(len(A), n):
		A.append(2 * (A[i - 5] + B[i - 5]) % mod)
		B.append((A[i - 1] + A[i - 5] + 2 * B[i - 5]) % mod)
	print(results[n] if n < 9 else (5 * A[n - 1] + 9 * A[n - 2] + 19 * A[n - 3] + 6 * A[n - 4] + 3 * A[n - 5] + 2 * B[n - 1] + 5 * B[n - 2] + 20 * B[n - 3] + 5 * B[n - 4] + 4 * B[n - 5]) % mod)


mod = 10 ** 9 + 7
A = [0, 0, 0, 0, 0, 2, 3, 15, 2, 0]
B = [0, 0, 0, 0, 0, 4, 9, 13, 17, 2]
results = [1, 9, 90, 303, 280, 218, 95, 101, 295]
for _ in range(int(input())):
	n = int(input())
	for i in range(len(A), n):
		A.append(2 * (A[i - 5] + B[i - 5]) % mod)
		B.append((A[i - 1] + A[i - 5] + 2 * B[i - 5]) % mod)
	print(results[n] if n < 9 else (5 * A[n - 1] + 9 * A[n - 2] + 19 * A[n - 3] + 6 * A[n - 4] + 3 * A[n - 5] + 2 * B[n - 1] + 5 * B[n - 2] + 20 * B[n - 3] + 5 * B[n - 4] + 4 * B[n - 5]) % mod)


mod = 10 ** 9 + 7
A = [0, 0, 0, 0, 0, 2, 3, 15, 2, 0]
B = [0, 0, 0, 0, 0, 4, 9, 13, 17, 2]
results = [1, 9, 90, 303, 280, 218, 95, 101, 295]
for _ in range(int(input())):
	n = int(input())
	for i in range(len(A), n):
		A.append(2 * (A[i - 5] + B[i - 5]) % mod)
		B.append((A[i - 1] + A[i - 5] + 2 * B[i - 5]) % mod)
	print(results[n] if n < 9 else (5 * A[n - 1] + 9 * A[n - 2] + 19 * A[n - 3] + 6 * A[n - 4] + 3 * A[n - 5] + 2 * B[n - 1] + 5 * B[n - 2] + 20 * B[n - 3] + 5 * B[n - 4] + 4 * B[n - 5]) % mod)


mod = 10 ** 9 + 7
A = [0, 0, 0, 0, 0, 2, 3, 15, 2, 0]
B = [0, 0, 0, 0, 0, 4, 9, 13, 17, 2]
results = [1, 9, 90, 303, 280, 218, 95, 101, 295]
for _ in range(int(input())):
	n = int(input())
	for i in range(len(A), n):
		A.append(2 * (A[i - 5] + B[i - 5]) % mod)
		B.append((A[i - 1] + A[i - 5] + 2 * B[i - 5]) % mod)
	print(results[n] if n < 9 else (5 * A[n - 1] + 9 * A[n - 2] + 19 * A[n - 3] + 6 * A[n - 4] + 3 * A[n - 5] + 2 * B[n - 1] + 5 * B[n - 2] + 20 * B[n - 3] + 5 * B[n - 4] + 4 * B[n - 5]) % mod)


mod = 10 ** 9 + 7
A = [0, 0, 0, 0, 0, 2, 3, 15, 2, 0]
B = [0, 0, 0, 0, 0, 4, 9, 13, 17, 2]
results = [1, 9, 90, 303, 280, 218, 95, 101, 295]
for _ in range(int(input())):
	n = int(input())
	for i in range(len(A), n):
		A.append(2 * (A[i - 5] + B[i - 5]) % mod)
		B.append((A[i - 1] + A[i - 5] + 2 * B[i - 5]) % mod)
	print(results[n] if n < 9 else (5 * A[n - 1] + 9 * A[n - 2] + 19 * A[n - 3] + 6 * A[n - 4] + 3 * A[n - 5] + 2 * B[n - 1] + 5 * B[n - 2] + 20 * B[n - 3] + 5 * B[n - 4] + 4 * B[n - 5]) % mod)


mod = 10 ** 9 + 7
A = [0, 0, 0, 0, 0, 2, 3, 15, 2, 0]
B = [0, 0, 0, 0, 0, 4, 9, 13, 17, 2]
results = [1, 9, 90, 303, 280, 218, 95, 101, 295]
for _ in range(int(input())):
	n = int(input())
	for i in range(len(A), n):
		A.append(2 * (A[i - 5] + B[i - 5]) % mod)
		B.append((A[i - 1] + A[i - 5] + 2 * B[i - 5]) % mod)
	print(results[n] if n < 9 else (5 * A[n - 1] + 9 * A[n - 2] + 19 * A[n - 3] + 6 * A[n - 4] + 3 * A[n - 5] + 2 * B[n - 1] + 5 * B[n - 2] + 20 * B[n - 3] + 5 * B[n - 4] + 4 * B[n - 5]) % mod)


mod = 10 ** 9 + 7
A = [0, 0, 0, 0, 0, 2, 3, 15, 2, 0]
B = [0, 0, 0, 0, 0, 4, 9, 13, 17, 2]
results = [1, 9, 90, 303, 280, 218, 95, 101, 295]
for _ in range(int(input())):
	n = int(input())
	for i in range(len(A), n):
		A.append(2 * (A[i - 5] + B[i - 5]) % mod)
		B.append((A[i - 1] + A[i - 5] + 2 * B[i - 5]) % mod)
	print(results[n] if n < 9 else (5 * A[n - 1] + 9 * A[n - 2] + 19 * A[n - 3] + 6 * A[n - 4] + 3 * A[n - 5] + 2 * B[n - 1] + 5 * B[n - 2] + 20 * B[n - 3] + 5 * B[n - 4] + 4 * B[n - 5]) % mod)


mod = 10 ** 9 + 7
A = [0, 0, 0, 0, 0, 2, 3, 15, 2, 0]
B = [0, 0, 0, 0, 0, 4, 9, 13, 17, 2]
results = [1, 9, 90, 303, 280, 218, 95, 101, 295]
for _ in range(int(input())):
	n = int(input())
	for i in range(len(A), n):
		A.append(2 * (A[i - 5] + B[i - 5]) % mod)
		B.append((A[i - 1] + A[i - 5] + 2 * B[i - 5]) % mod)
	print(results[n] if n < 9 else (5 * A[n - 1] + 9 * A[n - 2] + 19 * A[n - 3] + 6 * A[n - 4] + 3 * A[n - 5] + 2 * B[n - 1] + 5 * B[n - 2] + 20 * B[n - 3] + 5 * B[n - 4] + 4 * B[n - 5]) % mod)


mod = 10 ** 9 + 7
A = [0, 0, 0, 0, 0, 2, 3, 15, 2, 0]
B = [0, 0, 0, 0, 0, 4, 9, 13, 17, 2]
results = [1, 9, 90, 303, 280, 218, 95, 101, 295]
for _ in range(int(input())):
	n = int(input())
	for i in range(len(A), n):
		A.append(2 * (A[i - 5] + B[i - 5]) % mod)
		B.append((A[i - 1] + A[i - 5] + 2 * B[i - 5]) % mod)
	print(results[n] if n < 9 else (5 * A[n - 1] + 9 * A[n - 2] + 19 * A[n - 3] + 6 * A[n - 4] + 3 * A[n - 5] + 2 * B[n - 1] + 5 * B[n - 2] + 20 * B[n - 3] + 5 * B[n - 4] + 4 * B[n - 5]) % mod)


mod = 10 ** 9 + 7
A = [0, 0, 0, 0, 0, 2, 3, 15, 2, 0]
B = [0, 0, 0, 0, 0, 4, 9, 13, 17, 2]
results = [1, 9, 90, 303, 280, 218, 95, 101, 295]
for _ in range(int(input())):
	n = int(input())
	for i in range(len(A), n):
		A.append(2 * (A[i - 5] + B[i - 5]) % mod)
		B.append((A[i - 1] + A[i - 5] + 2 * B[i - 5]) % mod)
	print(results[n] if n < 9 else (5 * A[n - 1] + 9 * A[n - 2] + 19 * A[n - 3] + 6 * A[n - 4] + 3 * A[n - 5] + 2 * B[n - 1] + 5 * B[n - 2] + 20 * B[n - 3] + 5 * B[n - 4] + 4 * B[n - 5]) % mod)


import math
import os
import random
import re
import sys
mod = 10 ** 9 + 7
A = [0, 0, 0, 0, 0, 2, 3, 15, 2, 0]
B = [0, 0, 0, 0, 0, 4, 9, 13, 17, 2]
results = [1, 9, 90, 303, 280, 218, 95, 101, 295]
for _ in range(int(input())):
	n = int(input())
	for i in range(len(A), n):
		A.append(2 * (A[i - 5] + B[i - 5]) % mod)
		B.append((A[i - 1] + A[i - 5] + 2 * B[i - 5]) % mod)
	print(results[n] if n < 9 else (5 * A[n - 1] + 9 * A[n - 2] + 19 * A[n - 3] + 6 * A[n - 4] + 3 * A[n - 5] + 2 * B[n - 1] + 5 * B[n - 2] + 20 * B[n - 3] + 5 * B[n - 4] + 4 * B[n - 5]) % mod)


mod = 10 ** 9 + 7
A = [0, 0, 0, 0, 0, 2, 3, 15, 2, 0]
B = [0, 0, 0, 0, 0, 4, 9, 13, 17, 2]
results = [1, 9, 90, 303, 280, 218, 95, 101, 295]
for _ in range(int(input())):
	n = int(input())
	for i in range(len(A), n):
		A.append(2 * (A[i - 5] + B[i - 5]) % mod)
		B.append((A[i - 1] + A[i - 5] + 2 * B[i - 5]) % mod)
	print(results[n] if n < 9 else (5 * A[n - 1] + 9 * A[n - 2] + 19 * A[n - 3] + 6 * A[n - 4] + 3 * A[n - 5] + 2 * B[n - 1] + 5 * B[n - 2] + 20 * B[n - 3] + 5 * B[n - 4] + 4 * B[n - 5]) % mod)


mod = 10 ** 9 + 7
A = [0, 0, 0, 0, 0, 2, 3, 15, 2, 0]
B = [0, 0, 0, 0, 0, 4, 9, 13, 17, 2]
results = [1, 9, 90, 303, 280, 218, 95, 101, 295]
for _ in range(int(input())):
	n = int(input())
	for i in range(len(A), n):
		A.append(2 * (A[i - 5] + B[i - 5]) % mod)
		B.append((A[i - 1] + A[i - 5] + 2 * B[i - 5]) % mod)
	print(results[n] if n < 9 else (5 * A[n - 1] + 9 * A[n - 2] + 19 * A[n - 3] + 6 * A[n - 4] + 3 * A[n - 5] + 2 * B[n - 1] + 5 * B[n - 2] + 20 * B[n - 3] + 5 * B[n - 4] + 4 * B[n - 5]) % mod)


mod = 10 ** 9 + 7
A = [0, 0, 0, 0, 0, 2, 3, 15, 2, 0]
B = [0, 0, 0, 0, 0, 4, 9, 13, 17, 2]
results = [1, 9, 90, 303, 280, 218, 95, 101, 295]
for _ in range(int(input())):
	n = int(input())
	for i in range(len(A), n):
		A.append(2 * (A[i - 5] + B[i - 5]) % mod)
		B.append((A[i - 1] + A[i - 5] + 2 * B[i - 5]) % mod)
	print(results[n] if n < 9 else (5 * A[n - 1] + 9 * A[n - 2] + 19 * A[n - 3] + 6 * A[n - 4] + 3 * A[n - 5] + 2 * B[n - 1] + 5 * B[n - 2] + 20 * B[n - 3] + 5 * B[n - 4] + 4 * B[n - 5]) % mod)


import sys
primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43}

def canextend(l, s):
	(s, l) = (s + l % 10, l // 10)
	(s, l) = (s + l % 10, l // 10)
	if not s in primes:
		return False
	(s, l) = (s + l % 10, l // 10)
	if not s in primes:
		return False
	(s, l) = (s + l % 10, l // 10)
	if not s in primes:
		return False
	return True
last4digitmap = []
for i in range(10000):
	followups = []
	for j in range(10):
		if canextend(i, j):
			followups.append(i % 1000 * 10 + j)
	last4digitmap.append(followups)

def extend1(resultsofar):
	result = {}
	for (k, v) in resultsofar.items():
		for n in last4digitmap[k]:
			result[n] = result.setdefault(n, 0) + v
	return result

def good4(x):
	(a, x) = (x % 10, x // 10)
	(b, x) = (x % 10, x // 10)
	(c, x) = (x % 10, x // 10)
	d = x
	return a + b + c + d in primes and a + b + c in primes and (b + c + d in primes)
l = {x: 1 for x in range(1000, 10000) if good4(x)}
q = int(input().strip())
queries = []
for a0 in range(q):
	n = int(input().strip())
	queries.append(n)
todo = sorted(queries)
while todo[0] < 5:
	todo.pop(0)
cache = [0] * 400001
cache[1] = len(range(1, 10))
cache[2] = len(range(10, 100))
cache[3] = len([i for i in range(100, 1000) if sum([int(x) for x in str(i)]) in primes])
cache[4] = len([i for i in range(1000, 10000) if sum([int(x) for x in str(i)]) in primes and sum([int(x) for x in str(i)[:3]]) in primes and (sum([int(x) for x in str(i)[-3:]]) in primes)])
lastlength = 4
l = {x: 1 for x in range(1000, 10000) if good4(x)}
for stringlength in todo:
	stepstodo = stringlength - lastlength
	while stepstodo >= 1:
		l = extend1(l)
		stepstodo -= 1
	s = 0
	for (k, v) in l.items():
		l[k] = v % 1000000007
		s += v
	cache[stringlength] = s % 1000000007
	lastlength = stringlength
for n in queries:
	print(cache[n])


mod = 10 ** 9 + 7
A = [0, 0, 0, 0, 0, 2, 3, 15, 2, 0]
B = [0, 0, 0, 0, 0, 4, 9, 13, 17, 2]
results = [1, 9, 90, 303, 280, 218, 95, 101, 295]
for _ in range(int(input())):
	n = int(input())
	for i in range(len(A), n):
		A.append(2 * (A[i - 5] + B[i - 5]) % mod)
		B.append((A[i - 1] + A[i - 5] + 2 * B[i - 5]) % mod)
	print(results[n] if n < 9 else (5 * A[n - 1] + 9 * A[n - 2] + 19 * A[n - 3] + 6 * A[n - 4] + 3 * A[n - 5] + 2 * B[n - 1] + 5 * B[n - 2] + 20 * B[n - 3] + 5 * B[n - 4] + 4 * B[n - 5]) % mod)


mod = 10 ** 9 + 7
A = [0, 0, 0, 0, 0, 2, 3, 15, 2, 0]
B = [0, 0, 0, 0, 0, 4, 9, 13, 17, 2]
results = [1, 9, 90, 303, 280, 218, 95, 101, 295]
for _ in range(int(input())):
	n = int(input())
	for i in range(len(A), n):
		A.append(2 * (A[i - 5] + B[i - 5]) % mod)
		B.append((A[i - 1] + A[i - 5] + 2 * B[i - 5]) % mod)
	print(results[n] if n < 9 else (5 * A[n - 1] + 9 * A[n - 2] + 19 * A[n - 3] + 6 * A[n - 4] + 3 * A[n - 5] + 2 * B[n - 1] + 5 * B[n - 2] + 20 * B[n - 3] + 5 * B[n - 4] + 4 * B[n - 5]) % mod)


mod = 10 ** 9 + 7
A = [0, 0, 0, 0, 0, 2, 3, 15, 2, 0]
B = [0, 0, 0, 0, 0, 4, 9, 13, 17, 2]
results = [1, 9, 90, 303, 280, 218, 95, 101, 295]
for _ in range(int(input())):
	n = int(input())
	for i in range(len(A), n):
		A.append(2 * (A[i - 5] + B[i - 5]) % mod)
		B.append((A[i - 1] + A[i - 5] + 2 * B[i - 5]) % mod)
	print(results[n] if n < 9 else (5 * A[n - 1] + 9 * A[n - 2] + 19 * A[n - 3] + 6 * A[n - 4] + 3 * A[n - 5] + 2 * B[n - 1] + 5 * B[n - 2] + 20 * B[n - 3] + 5 * B[n - 4] + 4 * B[n - 5]) % mod)


mod = 10 ** 9 + 7
A = [0, 0, 0, 0, 0, 2, 3, 15, 2, 0]
B = [0, 0, 0, 0, 0, 4, 9, 13, 17, 2]
results = [1, 9, 90, 303, 280, 218, 95, 101, 295]
for _ in range(int(input())):
	n = int(input())
	for i in range(len(A), n):
		A.append(2 * (A[i - 5] + B[i - 5]) % mod)
		B.append((A[i - 1] + A[i - 5] + 2 * B[i - 5]) % mod)
	print(results[n] if n < 9 else (5 * A[n - 1] + 9 * A[n - 2] + 19 * A[n - 3] + 6 * A[n - 4] + 3 * A[n - 5] + 2 * B[n - 1] + 5 * B[n - 2] + 20 * B[n - 3] + 5 * B[n - 4] + 4 * B[n - 5]) % mod)


mod = 10 ** 9 + 7
A = [0, 0, 0, 0, 0, 2, 3, 15, 2, 0]
B = [0, 0, 0, 0, 0, 4, 9, 13, 17, 2]
results = [1, 9, 90, 303, 280, 218, 95, 101, 295]
for _ in range(int(input())):
	n = int(input())
	for i in range(len(A), n):
		A.append(2 * (A[i - 5] + B[i - 5]) % mod)
		B.append((A[i - 1] + A[i - 5] + 2 * B[i - 5]) % mod)
	print(results[n] if n < 9 else (5 * A[n - 1] + 9 * A[n - 2] + 19 * A[n - 3] + 6 * A[n - 4] + 3 * A[n - 5] + 2 * B[n - 1] + 5 * B[n - 2] + 20 * B[n - 3] + 5 * B[n - 4] + 4 * B[n - 5]) % mod)


mod = 10 ** 9 + 7
A = [0, 0, 0, 0, 0, 2, 3, 15, 2, 0]
B = [0, 0, 0, 0, 0, 4, 9, 13, 17, 2]
results = [1, 9, 90, 303, 280, 218, 95, 101, 295]
for _ in range(int(input())):
	n = int(input())
	for i in range(len(A), n):
		A.append(2 * (A[i - 5] + B[i - 5]) % mod)
		B.append((A[i - 1] + A[i - 5] + 2 * B[i - 5]) % mod)
	print(results[n] if n < 9 else (5 * A[n - 1] + 9 * A[n - 2] + 19 * A[n - 3] + 6 * A[n - 4] + 3 * A[n - 5] + 2 * B[n - 1] + 5 * B[n - 2] + 20 * B[n - 3] + 5 * B[n - 4] + 4 * B[n - 5]) % mod)


mod = 10 ** 9 + 7
A = [0, 0, 0, 0, 0, 2, 3, 15, 2, 0]
B = [0, 0, 0, 0, 0, 4, 9, 13, 17, 2]
results = [1, 9, 90, 303, 280, 218, 95, 101, 295]
for _ in range(int(input())):
	n = int(input())
	for i in range(len(A), n):
		A.append(2 * (A[i - 5] + B[i - 5]) % mod)
		B.append((A[i - 1] + A[i - 5] + 2 * B[i - 5]) % mod)
	print(results[n] if n < 9 else (5 * A[n - 1] + 9 * A[n - 2] + 19 * A[n - 3] + 6 * A[n - 4] + 3 * A[n - 5] + 2 * B[n - 1] + 5 * B[n - 2] + 20 * B[n - 3] + 5 * B[n - 4] + 4 * B[n - 5]) % mod)


mod = 10 ** 9 + 7
A = [0, 0, 0, 0, 0, 2, 3, 15, 2, 0]
B = [0, 0, 0, 0, 0, 4, 9, 13, 17, 2]
results = [1, 9, 90, 303, 280, 218, 95, 101, 295]
for _ in range(int(input())):
	n = int(input())
	for i in range(len(A), n):
		A.append(2 * (A[i - 5] + B[i - 5]) % mod)
		B.append((A[i - 1] + A[i - 5] + 2 * B[i - 5]) % mod)
	print(results[n] if n < 9 else (5 * A[n - 1] + 9 * A[n - 2] + 19 * A[n - 3] + 6 * A[n - 4] + 3 * A[n - 5] + 2 * B[n - 1] + 5 * B[n - 2] + 20 * B[n - 3] + 5 * B[n - 4] + 4 * B[n - 5]) % mod)


mod = 10 ** 9 + 7
A = [0, 0, 0, 0, 0, 2, 3, 15, 2, 0]
B = [0, 0, 0, 0, 0, 4, 9, 13, 17, 2]
results = [1, 9, 90, 303, 280, 218, 95, 101, 295]
for _ in range(int(input())):
	n = int(input())
	for i in range(len(A), n):
		A.append(2 * (A[i - 5] + B[i - 5]) % mod)
		B.append((A[i - 1] + A[i - 5] + 2 * B[i - 5]) % mod)
	print(results[n] if n < 9 else (5 * A[n - 1] + 9 * A[n - 2] + 19 * A[n - 3] + 6 * A[n - 4] + 3 * A[n - 5] + 2 * B[n - 1] + 5 * B[n - 2] + 20 * B[n - 3] + 5 * B[n - 4] + 4 * B[n - 5]) % mod)


mod = 10 ** 9 + 7
A = [0, 0, 0, 0, 0, 2, 3, 15, 2, 0]
B = [0, 0, 0, 0, 0, 4, 9, 13, 17, 2]
results = [1, 9, 90, 303, 280, 218, 95, 101, 295]
for _ in range(int(input())):
	n = int(input())
	for i in range(len(A), n):
		A.append(2 * (A[i - 5] + B[i - 5]) % mod)
		B.append((A[i - 1] + A[i - 5] + 2 * B[i - 5]) % mod)
	print(results[n] if n < 9 else (5 * A[n - 1] + 9 * A[n - 2] + 19 * A[n - 3] + 6 * A[n - 4] + 3 * A[n - 5] + 2 * B[n - 1] + 5 * B[n - 2] + 20 * B[n - 3] + 5 * B[n - 4] + 4 * B[n - 5]) % mod)


mod = 10 ** 9 + 7
A = [0, 0, 0, 0, 0, 2, 3, 15, 2, 0]
B = [0, 0, 0, 0, 0, 4, 9, 13, 17, 2]
results = [1, 9, 90, 303, 280, 218, 95, 101, 295]
for _ in range(int(input())):
	n = int(input())
	for i in range(len(A), n):
		A.append(2 * (A[i - 5] + B[i - 5]) % mod)
		B.append((A[i - 1] + A[i - 5] + 2 * B[i - 5]) % mod)
	print(results[n] if n < 9 else (5 * A[n - 1] + 9 * A[n - 2] + 19 * A[n - 3] + 6 * A[n - 4] + 3 * A[n - 5] + 2 * B[n - 1] + 5 * B[n - 2] + 20 * B[n - 3] + 5 * B[n - 4] + 4 * B[n - 5]) % mod)