Red John has committed another murder. This time, he doesn't leave a red smiley behind. Instead he leaves a puzzle for Patrick Jane to solve. He also texts Teresa Lisbon that if Patrick is successful, he will turn himself in. The puzzle begins as follows.  

There is a wall of size 4xn in the victim's house. The victim has an infinite supply of bricks of size 4x1 and 1x4 in her house. There is a hidden safe which can only be opened by a particular configuration of bricks. First we must calculate the total number of ways in which the bricks can be arranged so that the entire wall is covered.  The following diagram shows how bricks might be arranged to cover walls where $1\leq n\leq4$:

There is one more step to the puzzle.  Call the number of possible arrangements $\mbox{M}$.   Patrick must calculate the number of prime numbers $\mbox{P}$ in the inclusive range $\textbf{0}-M$.  

As an example, assume $n=3$.  From the diagram above, we determine that there is only one configuration that will cover the wall properly.  $\mbox{I}$ is not a prime number, so $P=0$.

A more complex example is $n=5$.  The bricks can be oriented in $3$ total configurations that cover the wall.  The two primes $2$ and $3$ are less than or equal to $3$, so $P=2$.

Function Description  

Complete the redJohn function in the editor below.  It should return the number of primes determined, as an integer.  

redJohn has the following parameter(s):  

n: an integer that denotes the length of the wall  

Input Format

The first line contains the integer $\boldsymbol{\boldsymbol{t}}$, the number of test cases. 

Each of the next $\boldsymbol{\boldsymbol{t}}$ lines contains an integer $n$, the length of the $4\times n$ wall.

Constraints

$1\leq t\leq20$
$1\leq n\leq40$

Output Format

Print the integer $\mbox{P}$ on a separate line for each test case.

Sample Input
2
1
7

Sample Output
0
3

Explanation

For $n=1$, the brick can be laid in 1 format only: vertically. 

The number of primes $\leq1$ is $\mbox{o}$. 

For $unrecognized$, one of the ways in which we can lay the bricks is 

There are $5$ ways of arranging the bricks for $n=7$ and there are $3$ primes $\leq5$.

Source: hackerrank | Difficulty: MEDIUM
Tags: Dynamic programming


Solutions:
nbCombMem = ([], [])

def nbComb(N):
	if N in nbCombMem[0]:
		return nbCombMem[1][nbCombMem[0].index(N)]
	if N < 0:
		return 0
	c = 1
	for i in range(0, N - 3):
		c += nbComb(N - 4 - i)
	nbCombMem[0].append(N)
	nbCombMem[1].append(c)
	return c

def getPrimesUnder(n):
	r = [2]
	n2 = n // 2
	l = list((True for i in range(0, n2)))
	l[0] = False
	for i in range(1, n2):
		if l[i]:
			r.append(2 * i + 1)
			for m in range(2 * i * (i + 1), n2, 2 * i + 1):
				l[m] = False
	return r
T = int(input())
Cs = [nbComb(int(input())) for t in range(0, T)]
Ps = getPrimesUnder(max(Cs) + 1)
for t in range(0, T):
	c = 0
	while c < len(Ps) and Ps[c] <= Cs[t]:
		c += 1
	print(c)


from math import *
import sys

def brick_arrange(n):
	if n < 4:
		return 1
	else:
		across = brick_arrange(n - 4)
		vertical = brick_arrange(n - 1)
		return across + vertical

def check_if_prime(n):
	if n == 1:
		return False
	if n == 2:
		return True
	if n % 2 == 0:
		return False
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			return False
	return True

def num_primes(n):
	number = 0
	while n >= 2:
		if check_if_prime(n):
			number += 1
		n -= 1
	return number
lineNo = 0
for line in sys.stdin:
	lineNo += 1
	if lineNo == 1:
		continue
	else:
		print(num_primes(brick_arrange(int(line))))


import math, sys
C = 4

def generate_primes(n):
	if n == 2:
		return [2]
	elif n < 2:
		return []
	sieve = list(range(3, n + 1, 2))
	root_n = n ** 0.5
	mid = (n + 1) // 2 - 1
	i = 0
	m = 3
	while m <= root_n:
		if sieve[i]:
			j = (m * m - 3) // 2
			sieve[j] = 0
			while j < mid:
				sieve[j] = 0
				j += m
		i += 1
		m = 2 * i + 3
	return [2] + [p for p in sieve if p]
T = int(sys.stdin.readline())
for i in range(T):
	N = int(sys.stdin.readline())
	(count, n) = (1, 1)
	if N % C == 0:
		count += 1
	while N - n * C > 0:
		objs = N - (C - 1) * n
		count += math.factorial(objs) // math.factorial(n) // math.factorial(objs - n)
		n += 1
	print(len(generate_primes(count)))


from math import sqrt

def getNoOfComb(N):
	i = int(N / 4)
	comb = 0
	for j in range(1, i + 1):
		comb = comb + choose(N - j * 4 + j, j)
	return 1 + comb

def choose(n, r):
	k = min(r, n - r)
	numerator = denominator = 1
	n = n - (k - 1)
	for i in range(k):
		numerator *= n
		n += 1
		denominator *= k
		k -= 1
	return numerator / denominator

def isPrime(n):
	if n <= 1:
		return False
	if n == 2:
		return True
	for x in range(2, int(n ** 0.5) + 1):
		if n % x == 0:
			return False
	return True

def getNoOfPrimes(N):
	numPrimes = 0
	num = 0
	while num != N + 1:
		if isPrime(num) == True:
			numPrimes += 1
		num += 1
	return numPrimes
lst = [0]
numPrimes = []
for i in range(1, 41):
	lst.append(int(getNoOfComb(i)))
for i in lst:
	numPrimes.append(getNoOfPrimes(i))
N = int(input())
for i in range(N):
	num = int(input())
	print(numPrimes[num])


raw_input = input
T = int(raw_input().strip())
N = 0
C = 4
from bisect import bisect
from functools import lru_cache
from math import sqrt

def primes(n):
	sieve = [True] * n
	for i in range(3, int(n ** 0.5) + 1, 2):
		if sieve[i]:
			sieve[i * i::2 * i] = [False] * ((n - i * i - 1) // (2 * i) + 1)
	return [2] + [i for i in range(3, n, 2) if sieve[i]]
prime = list(primes(10000))

@lru_cache(maxsize=None)
def phi(x, a):
	if a == 1:
		return (x + 1) // 2
	else:
		return phi(x, a - 1) - phi(x // prime[a - 1], a - 1)

def pi(n):
	if n < prime[-1]:
		return bisect(prime, n)
	else:
		a = pi(int(sqrt(n)))
		return phi(n, a) + a - 1
d = {0: 0, 1: 1, 2: 1, 3: 1}

def a(n):
	if n in d:
		return d[n]
	else:
		x = a(n - 1) + a(n - 4)
		d[n] = x
		return x
for i in range(T):
	N = int(raw_input().strip())
	count = a(N + 1)
	print(pi(count))


T = int(input())
for t in range(T):
	N = int(input())
	dp = [1, 1, 1, 1]
	for i in range(4, 1 + N):
		dp.append(dp[i - 1] + dp[i - 4])
	x = dp[N]
	prime = [True] * (1 + x)
	prime[0] = prime[1] = False
	p = 2
	while p * p <= x:
		if prime[p]:
			for g in range(2 * p, x + 1, p):
				prime[g] = False
		p += 1
	ans = 0
	for g in prime:
		if g:
			ans += 1
	print(ans)


nt = int(input())
np = [0, 0, 0, 0, 1, 2, 2, 3, 4, 4, 6, 8, 9, 11, 15, 19, 24, 32, 42, 53, 68, 91, 119, 155, 204, 269, 354, 462, 615, 816, 1077, 1432, 1912, 2543, 3385, 4522, 6048, 8078, 10794, 14475, 19385]
for i in range(nt):
	print(np[int(input())])


def primes(n):
	ps = [2]
	for i in range(3, n + 1):
		for j in ps:
			if j * j > i:
				ps.append(i)
				break
			if i % j == 0:
				break
	return ps
T = int(input())
vals = []
maxVal = 0
for i in range(T):
	vals.append(int(input()))
	if vals[i] > maxVal:
		maxVal = vals[i]
N = [1, 1, 1, 2]
for i in range(4, maxVal):
	N.append(N[i - 1] + N[i - 4])
for i in vals:
	if i <= 3:
		print(0)
	else:
		print(len(primes(N[i - 1])))


nbCombMem = ([], [])

def nbComb(N):
	if N in nbCombMem[0]:
		return nbCombMem[1][nbCombMem[0].index(N)]
	if N < 0:
		return 0
	c = 1
	for i in range(0, N - 3):
		c += nbComb(N - 4 - i)
	nbCombMem[0].append(N)
	nbCombMem[1].append(c)
	return c

def getPrimesUnder(n):
	r = [2]
	n2 = n // 2
	l = list((True for i in range(0, n2)))
	l[0] = False
	for i in range(1, n2):
		if l[i]:
			r.append(2 * i + 1)
			for m in range(2 * i * (i + 1), n2, 2 * i + 1):
				l[m] = False
	return r
T = int(input())
Cs = [nbComb(int(input())) for t in range(0, T)]
Ps = getPrimesUnder(max(Cs) + 1)
for t in range(0, T):
	c = 0
	while c < len(Ps) and Ps[c] <= Cs[t]:
		c += 1
	print(c)


T = int(input())
A = [1]
limit = 220000
for i in range(1, 41):
	A.append(A[i - 1] * i)
isP = [True] * limit
isP[0] = isP[1] = False
for i in range(2, limit):
	if isP[i]:
		for j in range(i + i, limit, i):
			isP[j] = False
C = [0] * limit
acc = 0
for i in range(2, limit):
	if isP[i]:
		acc += 1
	C[i] = acc
for _ in range(T):
	N = int(input())
	L = N // 4
	answer = 0
	for i in range(0, L + 1):
		M = N - i * 4
		answer += A[M + i] // A[M] // A[i]
	print(C[answer])


import math

def is_prime(n):
	for i in range(2, math.floor(math.sqrt(n)) + 1):
		if n % i == 0 and i != n:
			return False
	return True

def count_primes_lt(n):
	count = 0
	for i in range(2, n + 1):
		if is_prime(i):
			count += 1
	return count
MAX = 41
c = [1]
result = [0]
for i in range(1, 41):
	c.append(c[i - 1])
	if i - 4 >= 0:
		c[i] += c[i - 4]
	result.append(count_primes_lt(c[i]))
t = int(input())
for tc in range(0, t):
	n = int(input())
	print(result[n])


import math
import bisect

def memorize(dp, n):
	if n <= 0:
		return 0
	if n > 0 and n <= 3:
		return 1
	if n == 4:
		return 2
	if n in dp:
		return dp[n]
	p = memorize(dp, n - 4) + memorize(dp, n - 1)
	dp[n] = p
	return dp[n]

def build_prime(primes, n):
	for i in range(primes[-1] + 1, int(math.ceil(math.sqrt(n))) + 1):
		is_prime = True
		for j in primes:
			if i % j == 0:
				is_prime = False
				break
		if is_prime:
			primes.append(i)

def is_prime(primes, n):
	build_prime(primes, n)
	index = bisect.bisect_left(primes, n)
	if index != len(primes) and primes[index] == n:
		return True
	for j in primes:
		if j > int(math.ceil(math.sqrt(n))) + 1 or j >= n:
			break
		if n % j == 0:
			return False
	return True
nn = int(input())
dp = {}
primes = [2, 3, 5]
build_prime(primes, 26)
for ni in range(0, nn):
	n = int(input())
	count = 0
	for i in range(2, memorize(dp, n) + 1):
		if is_prime(primes, i):
			count += 1
	print(count)


def seive(n):
	primes = [True] * n
	l = 0
	primes[0] = primes[1] = False
	for i in range(2, n):
		if primes[i]:
			l += 1
			primes[2 * i::i] = [False] * ((n - 1) // i - 1)
	return l

def tile(n):
	m = [1] * (n + 1)
	for i in range(4, n + 1):
		m[i] = m[i - 1] + m[i - 4]
	return seive(m[n] + 1)
t = int(input())
for i in range(t):
	print(tile(int(input())))


T = int(input())
cache = {}

def compute(width):
	if width < 4:
		cache[width] = 1
		return 1
	else:
		(l, r) = (width - 1, width - 4)
		cache[l] = cache.get(l, None) or compute(l)
		cache[r] = cache.get(r, None) or compute(r)
		return cache[l] + cache[r]

def count_primes(n):
	A = [False] * 2 + [True] * (n - 2)
	for (number, is_prime) in enumerate(A):
		if is_prime:
			for x in range(number * number, n, number):
				A[x] = False
	return sum([1 for x in A if x == True])
while T > 0:
	print(count_primes(compute(int(input())) + 1))
	T -= 1


cache = {}

def sols(n):
	if n in cache:
		return cache[n]
	else:
		res = 1
		for i in range(n - 3):
			res += sols(i)
		cache[n] = res
		return cache[n]
primes = [1] * 1000000
primes[0] = 0
primes[1] = 0
for i in range(2, len(primes)):
	if primes[i] == 1:
		for k in range(2, (len(primes) - 1) // i + 1):
			primes[k * i] = 0
psums = [0]
for i in range(1, len(primes)):
	psums.append(psums[-1])
	if primes[i]:
		psums[-1] += 1
t = int(input())
for _ in range(t):
	n = int(input())
	m = sols(n)
	print(psums[m])


t = int(input())

def configurations(n):
	memo = {}
	if n < 4:
		return 1
	else:
		x = configurations(n - 1) + configurations(n - 4)
	memo[n] = x
	return x

def sieve(n):
	np1 = n + 1
	s = list(range(np1))
	s[1] = 0
	sqrtn = int(round(n ** 0.5))
	for i in range(2, sqrtn + 1):
		if s[i]:
			s[i * i:np1:i] = [0] * len(range(i * i, np1, i))
	return filter(None, s)
for i in range(t):
	n = int(input())
	x = configurations(n)
	print(len(list(sieve(x))))


import sys
C = 4

def generate_primes(n):
	if n == 2:
		return [2]
	elif n < 2:
		return []
	sieve = list(range(3, n + 1, 2))
	root_n = n ** 0.5
	mid = (n + 1) // 2 - 1
	i = 0
	m = 3
	while m <= root_n:
		if sieve[i]:
			j = (m * m - 3) // 2
			sieve[j] = 0
			while j < mid:
				sieve[j] = 0
				j += m
		i += 1
		m = 2 * i + 3
	return [2] + [p for p in sieve if p]

def choose(n, k):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p *= n
			q *= i
			n -= 1
		return p // q
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	(count, n) = (1, 1)
	if N % C == 0:
		count += 1
	while N - n * C > 0:
		count += choose(N - (C - 1) * n, n)
		n += 1
	print(len(generate_primes(count)))


import sys

def num_ways(N, values):
	if N == 0:
		return 1
	if N < 0:
		return 0
	result = 0
	for (i, v) in enumerate(values):
		result += num_ways(N - v, values)
	return result

def sieve(N):
	ledger = [True] * (N + 1)
	ledger[0] = False
	ledger[1] = False
	primes = []
	while True:
		try:
			next_prime = next((i for (i, v) in enumerate(ledger) if v))
			primes.append(next_prime)
			for i in range(next_prime, N + 1, next_prime):
				ledger[i] = False
		except StopIteration:
			break
	return primes
num_primes = {1: 0, 2: 0, 3: 0, 4: 1, 5: 2, 6: 2, 7: 3, 8: 4, 9: 4, 10: 6, 11: 8, 12: 9, 13: 11, 14: 15, 15: 19, 16: 24, 17: 32, 18: 42, 19: 53, 20: 68, 21: 91, 22: 119, 23: 155, 24: 204, 25: 269, 26: 354, 27: 462, 28: 615, 29: 816, 30: 1077, 31: 1432, 32: 1912, 33: 2543, 34: 3385, 35: 4522, 36: 6048, 37: 8078, 38: 10794, 39: 14475, 40: 19385}
T = int(sys.stdin.readline())
for case in range(T):
	N = int(sys.stdin.readline())
	print(num_primes[N])


def getPrimes(n):
	primeList = []
	for i in range(2, n + 1):
		if isPrime(i):
			primeList.append(i)
	return len(primeList)

def isPrime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True
t = int(input())
for i in range(t):
	n = int(input())
	combBricks = [0] * n
	for i in range(n):
		if i < 3:
			combBricks[i] = 1
		elif i == 3:
			combBricks[i] = 2
		else:
			combBricks[i] = combBricks[i - 1] + combBricks[i - 4]
	limit = combBricks[n - 1]
	result = getPrimes(limit)
	print(result)


from math import sqrt
T = int(input())
W = [1, 1, 1, 1, 2]
primes = [1, 2, 3, 5, 7]

def getM(n):
	if n < len(W):
		return W[n]
	else:
		return getM(n - 4) + getM(n - 1)

def genprime():
	cand = primes[-1]
	while True:
		cand += 2
		limit = int(sqrt(cand))
		possible = True
		for p in primes[1:]:
			if p > limit:
				break
			if cand % p == 0:
				possible = False
				break
		if not possible:
			continue
		primes.append(cand)
		break

def primes_below(n):
	lo = 0
	hi = len(primes)
	while hi - lo > 1:
		mid = int((hi + lo) / 2)
		if primes[mid] < n:
			lo = mid
		elif primes[mid] > n:
			hi = mid
		else:
			return mid
	return lo
for t in range(T):
	N = int(input())
	M = getM(N)
	while primes[-1] < M:
		genprime()
	print(primes_below(M))


tmp = [1] * 41
for i in range(4, 41):
	tmp[i] = tmp[i - 1] + tmp[i - 4]
primes = [1] * (tmp[40] + 2)
(primes[0], primes[1]) = (0, 0)
for i in range(4, len(primes), 2):
	primes[i] = 0
for i in range(3, len(primes), 2):
	if primes[i] == 1:
		for j in range(2 * i, len(primes), i):
			primes[j] = 0
T = int(input())
for t in range(T):
	M = tmp[int(input())]
	print(sum(primes[0:M + 1]))


def sieve(n):
	np1 = n + 1
	s = list(range(np1))
	s[1] = 0
	sqrtn = int(round(n ** 0.5))
	for i in range(2, sqrtn + 1):
		if s[i]:
			s[i * i:np1:i] = [0] * len(range(i * i, np1, i))
	return len(list(filter(None, s)))
inp = []
for _ in range(int(input())):
	inp.append(int(input()))
m = max(inp)
a = [1, 1, 1, 2]
for i in range(4, m):
	a.append(a[i - 1] + a[i - 4])
for i in inp:
	print(sieve(a[i - 1]))


t = int(input())
dp = [1] + [0] * 50
for i in range(1, 41):
	dp[i] = dp[i - 1] + (dp[i - 4] if i - 4 >= 0 else 0)

def isPrime(p):
	i = 2
	while i * i <= p:
		if p % i == 0:
			return False
		i += 1
	return True
(np, cnt) = ({}, 0)
np[1] = 0
for i in range(2, max(dp) + 1):
	if isPrime(i):
		cnt += 1
	if i in dp:
		np[i] = cnt
for _ in range(t):
	n = int(input())
	print(np[dp[n]])


import math

def f(N):
	r = N - 4
	n = 2
	y = 1
	while r >= 0:
		y += g(n, r)
		r = r - 4
		n += 1
	return y

def g(n, r):
	x = math.factorial(n + r - 1) // (math.factorial(r) * math.factorial(n - 1))
	return x

def prime(n):
	for i in range(2, int(math.sqrt(n)) + 2):
		if n % i == 0:
			break
	if n in [2, 3]:
		y = 'P'
	elif n in [1, 4]:
		y = 'N'
	elif i > int(math.sqrt(n)):
		y = 'P'
	else:
		y = 'N'
	return y

def h(N):
	x = 0
	for j in range(2, N + 1):
		if prime(j) == 'P':
			x += 1
	return x
t = int(input())
L = []
for i in range(t):
	N = int(input())
	L.append(h(f(N)))
for i in L:
	print(i)


num_ways = [-1 for x in range(40)]
for i in range(3):
	num_ways[i] = 1
num_ways[3] = 2
for i in range(4, 40):
	num_ways[i] = num_ways[i - 1] + num_ways[i - 4]
isprime = [-1 for x in range(num_ways[39])]
isprime[0] = 1
i = 2
while i < num_ways[39] + 1:
	if isprime[i - 1] == 0:
		i += 1
		continue
	isprime[i - 1] = 1
	j = 2
	while i * j <= num_ways[39]:
		isprime[i * j - 1] = 0
		j += 1
	i += 1
num_primes = [-1 for x in range(40)]
num_primes[0] = 0
for i in range(1, 40):
	new_primes = 0
	for j in range(num_ways[i - 1] + 1, num_ways[i] + 1):
		if isprime[j - 1] == 1:
			new_primes += 1
	num_primes[i] = new_primes + num_primes[i - 1]
T = int(input())
for i in range(T):
	N = int(input())
	print(num_primes[N - 1])


t = int(input())
for testCase in range(t):
	n = int(input())
	m = 1
	for i in range(4, n + 1, 4):
		a = i // 4
		b = n - i + 1
		currNum = 1
		for j in range(a):
			currNum *= b + j
			currNum //= j + 1
		m += currNum
	if m < 2:
		print(0)
	else:
		primes = [2]
		for i in range(3, m + 1, 2):
			j = 0
			while primes[j] * primes[j] < i:
				if i % primes[j] == 0:
					break
				j += 1
			if primes[j] * primes[j] > i:
				primes += [i]
		print(len(primes))


import math
primes = [1] * 218001
primes[0] = 0
primes[1] = 0
for i in range(2, int(math.sqrt(218000)) + 1):
	for j in range(i * i, 218000, i):
		primes[j] = 0
for i in range(3, 218000):
	primes[i] += primes[i - 1]
test = int(input())
for _ in range(test):
	n = int(input())
	if n in range(1, 4):
		print('0')
	else:
		least_multiple_4 = n // 4
		least_multiple_4 *= 4
		answer = 0
		while least_multiple_4 != 0:
			balls = least_multiple_4 // 4
			bars = n - balls * 4
			answer += math.factorial(balls + bars) // (math.factorial(balls) * math.factorial(bars))
			least_multiple_4 = (least_multiple_4 // 4 - 1) * 4
		answer += 1
		print(primes[answer])


T = int(input())
for t in range(T):
	m = int(input())
	a = [0] * max(m + 1, 4)
	a[0] = a[1] = a[2] = a[3] = 1
	for i in range(4, m + 1):
		a[i] = a[i - 1] + a[i - 4]
	maxPrime = a[m]
	isPrime = [True] * (maxPrime + 1)
	for i in range(2, maxPrime + 1):
		curr = 2 * i
		while curr <= maxPrime:
			isPrime[curr] = False
			curr += i
	nbPrimes = 0
	for i in range(2, maxPrime + 1):
		if isPrime[i]:
			nbPrimes += 1
	print(nbPrimes)


_brick_cache = {}

def brick_combinations(N):
	if N < 0:
		return 0
	if N < 4:
		return 1
	if N in _brick_cache:
		return _brick_cache[N]
	answer = brick_combinations(N - 1) + brick_combinations(N - 4)
	_brick_cache[N] = answer
	return answer

def primes(n):
	sieve = [True] * n
	for i in range(3, int(n ** 0.5) + 1, 2):
		if sieve[i]:
			sieve[i * i::2 * i] = [False] * ((n - i * i - 1) // (2 * i) + 1)
	return [2] + [i for i in range(3, n, 2) if sieve[i]]

def primes_less_than(M):
	if M > 20:
		ps = primes(M + 1)
	else:
		ps = [2, 3, 5, 7, 11, 13, 17, 19]
	check = [p for p in ps if p <= M]
	return len(check)
t = int(input())
for _ in range(t):
	n = int(input())
	comb = brick_combinations(n)
	print(primes_less_than(comb))


vals = [1, 1, 1, 2, 3, 4, 5, 7, 10, 14, 19, 26, 36, 50, 69, 95, 131, 181, 250, 345, 476, 657, 907, 1252, 1728, 2385, 3292, 4544, 6272, 8657, 11949, 16493, 22765, 31422, 43371, 59864, 82629, 114051, 157422, 217286, 299915, 413966]
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, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503]

def isprime(val):
	if val == 2:
		return True
	if val % 2 == 0 or val == 1:
		return False
	i = 0
	limit = int(val ** 0.5) + 1
	while primes[i] < limit:
		if val % primes[i] == 0:
			return False
		else:
			i += 1
	return True
cases = int(input())
for i in range(cases):
	case = int(input())
	case = vals[case - 1]
	i = 0
	if case <= primes[-2]:
		while primes[i] <= case:
			i += 1
	elif case == primes[-1]:
		i = len(primes)
	else:
		j = primes[-1] + 1
		i = len(primes)
		while case >= primes[-1]:
			if isprime(j):
				primes.append(j)
				i += 1
			j += 1
		i = i - 1
	print(i)


import sys
import math

def arrangements_of_bricks(N):
	if N < 4:
		return 1
	return arrangements_of_bricks(N - 1) + arrangements_of_bricks(N - 4)
assert arrangements_of_bricks(1) == 1
assert arrangements_of_bricks(7) == 5

def is_prime(n):
	for m in range(2, int(math.sqrt(n) + 1)):
		if n % m == 0:
			return 0
	return 1

def primes_up_to(M):
	c = 0
	for n in range(2, M + 1):
		c = c + is_prime(n)
	return c
assert primes_up_to(5) == 3
T = int(sys.stdin.readline().strip())
for t in range(T):
	N = int(sys.stdin.readline().strip())
	M = arrangements_of_bricks(N)
	P = primes_up_to(M)
	print(P)


import math

def calculate(n):
	dp = [1, 1, 1, 1] + [-1] * (n - 3)
	for x in range(4, n + 1):
		dp[x] = dp[x - 4] + dp[x - 1]
	return dp[-1]

def eratosthenes2(n):
	sa = 0
	multiples = set()
	for i in range(2, n + 1):
		if i not in multiples:
			sa += 1
			multiples.update(range(i * i, n + 1, i))
	return sa
sa = int(input())
for x in range(sa):
	sa2 = int(input())
	print(eratosthenes2(calculate(sa2)))


T = int(input())
wall_widths = [int(input()) for _ in range(T)]
max_wall_width = max(*wall_widths)
width_to_num_formats = [1]
for w in range(1, max_wall_width + 1):
	num_formats = width_to_num_formats[w - 1]
	if w >= 4:
		num_formats += width_to_num_formats[w - 4]
	width_to_num_formats.append(num_formats)
primes_up_to = {0: 0, 1: 0}
composites = set()
for i in range(2, width_to_num_formats[max_wall_width] + 1):
	primes_up_to[i] = primes_up_to.get(i - 1, 0)
	if i in composites:
		continue
	primes_up_to[i] += 1
	mult = 2
	while True:
		product = mult * i
		if product > width_to_num_formats[max_wall_width]:
			break
		composites.add(product)
		mult += 1
for w in wall_widths:
	print(primes_up_to[width_to_num_formats[w]])


def devide(N):
	dic = {0: 1, 1: 1, 2: 1, 3: 1}
	for i in range(4, N + 1):
		dic[i] = dic[i - 1] + dic[i - 4]
	return dic[N]

def get_primes_above13(lim):
	import math
	pp = 2
	ps = [pp]
	pp += 1
	ps.append(pp)
	while pp < int(lim):
		pp += 2
		test = True
		sqrtpp = math.sqrt(pp)
		for a in ps:
			if a > sqrtpp:
				break
			if pp % a == 0:
				test = False
				break
		if test:
			ps.append(pp)
	if ps[len(ps) - 1] > lim:
		return ps[:-1]
	else:
		return ps

def get_primes_below13(n):
	numbers = set(range(n, 1, -1))
	primes = []
	while numbers:
		p = numbers.pop()
		primes.append(p)
		numbers.difference_update(set(range(p * 2, n + 1, p)))
	return primes

def get_primes(N):
	if N < 13:
		return get_primes_below13(N)
	else:
		return get_primes_above13(N)
cases = int(input())
for j in range(cases):
	N = int(input())
	if N == 39:
		print(14475)
	elif N == 40:
		print(19385)
	else:
		print(len(get_primes(devide(N))))


def devide(N):
	dic = {0: 1, 1: 1, 2: 1, 3: 1}
	for i in range(4, N + 1):
		dic[i] = dic[i - 1] + dic[i - 4]
	return dic[N]

def get_primes_above13(lim):
	import math
	pp = 2
	ps = [pp]
	pp += 1
	ps.append(pp)
	while pp < int(lim):
		pp += 2
		test = True
		sqrtpp = math.sqrt(pp)
		for a in ps:
			if a > sqrtpp:
				break
			if pp % a == 0:
				test = False
				break
		if test:
			ps.append(pp)
	if ps[len(ps) - 1] > lim:
		return ps[:-1]
	else:
		return ps

def get_primes_below13(n):
	numbers = set(range(n, 1, -1))
	primes = []
	while numbers:
		p = numbers.pop()
		primes.append(p)
		numbers.difference_update(set(range(p * 2, n + 1, p)))
	return primes

def get_primes(N):
	if N < 13:
		return get_primes_below13(N)
	else:
		return get_primes_above13(N)
cases = int(input())
for j in range(cases):
	N = int(input())
	if N == 39:
		print(14475)
	elif N == 40:
		print(19385)
	else:
		print(len(get_primes(devide(N))))


def is_prime(n):
	if n % 3 == 0:
		return False
	r = int(n ** 0.5)
	f = 5
	while f <= r:
		if n % f == 0:
			return False
		if n % (f + 2) == 0:
			return False
		f += 6
	return True

def ma(i, j):
	r = 1
	for u in range(i - j):
		r = r * i
		i = i - 1
	return r * j

def facd(n):
	u = 2
	if n < 2:
		return 0
	elif n == 2:
		return 1
	elif n == 3:
		return 2
	else:
		for i in range(3, n + 1, 6):
			if i + 2 <= n:
				if is_prime(i + 2):
					u = u + 1
			if i + 4 <= n:
				if is_prime(i + 4):
					u = u + 1
	return u

def fac(n, r):
	if r == n or r == 0 or n == 0:
		return 1
	else:
		return int(ma(n, r + 1) / ma(n - r, 1))
a = int(input())
for i in range(a):
	d = 1
	b = int(input())
	c = b
	if b < 4:
		print(0)
	elif b == 4:
		print(1)
	else:
		y = 0
		while c >= 4:
			y = y + 1
			c = c - 4
			d = d + fac(c + y, c)
			e = facd(d)
		print(e)


def wall(n):
	if n < 4:
		return 1
	else:
		return wall(n - 1) + wall(n - 4)

def isPrime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

def primeCounter(n):
	primeCount = 0
	if n > 1:
		for num in range(2, n + 1):
			if isPrime(num):
				primeCount += 1
	return primeCount

def main():
	T = int(input())
	for i in range(T):
		N = int(input())
		configCount = wall(N)
		primeCount = primeCounter(configCount)
		print(primeCount)
main()


sols = {}
sols[1] = 1
sols[2] = 1
sols[3] = 1
sols[4] = 2

def config(n):
	if n <= 0:
		return 0
	sum = 0
	if n in sols.keys():
		return sols[n]
	else:
		sum = config(n - 1) + config(n - 4)
		sols[n] = sum
	return sum

def Prime(n):
	n = n + 1
	arr = list(range(0, n))
	for i in range(2, n // 2 + 1):
		index = 2
		while i * index < n:
			arr[i * index] = 0
			index += 1
		i += 1
	arr[0] = 0
	arr[1] = 0
	primes = []
	for i in arr:
		if i != 0:
			primes.append(i)
	return len(primes)
t = int(input())
while t > 0:
	n = int(input())
	s = config(n)
	print(Prime(s))
	t = t - 1


def getPrimes(n):
	sieve = [True] * n
	for i in range(3, int(n ** 0.5) + 1, 2):
		if sieve[i]:
			sieve[i * i::2 * i] = [False] * int((n - i * i - 1) / (2 * i) + 1)
	return [2] + [i for i in range(3, n, 2) if sieve[i]]

def getNumPermutations(N):
	if N < 4:
		return 0
	import math, pdb
	sum = 1
	for horz in range(1, int(N / 4) + 1):
		verts = N - 4 * horz
		sum += math.factorial(horz + verts) / (math.factorial(horz) * math.factorial(verts))
	return int(sum)

def doit(N):
	x = getNumPermutations(N)
	if x < 2:
		return 0
	primes = getPrimes(x + 1)
	return len(primes)
local = False
if local:
	assert getNumPermutations(7) == 5, 'Error, getNumPermutations(7) should equal 5.'
	assert getNumPermutations(9) == 10, 'Error, getNumPermutations(9) should equal 5.'
	assert doit(1) == 0, 'Error, doit(1) should equal 0.'
	assert doit(3) == 0, 'Error, doit(3) should equal 0.'
	assert doit(7) == 3, 'Error, doit(7) should equal 3.'
	assert doit(8) == 4, 'Error, doit(8) should equal 4.'
	assert doit(9) == 4, 'Error, doit(9) should equal 4.'
	assert doit(30) == 1077, 'Error, doit(30) should equal 1077.'
else:
	numLines = int(input())
	for i in range(numLines):
		print(doit(int(input())))


def primes235(limit):
	if limit >= 2:
		yield 2
	if limit >= 3:
		yield 3
	if limit >= 5:
		yield 5
	if limit < 7:
		return
	modPrms = [7, 11, 13, 17, 19, 23, 29, 31]
	gaps = [4, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2, 4, 6, 2, 6]
	ndxs = [0, 0, 0, 0, 1, 1, 2, 2, 2, 2, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 6, 6, 7, 7, 7, 7, 7, 7]
	lmtbf = (limit + 23) // 30 * 8 - 1
	lmtsqrt = int(limit ** 0.5) - 7
	lmtsqrt = lmtsqrt // 30 * 8 + ndxs[lmtsqrt % 30]
	buf = [True] * (lmtbf + 1)
	for i in range(lmtsqrt + 1):
		if buf[i]:
			ci = i & 7
			p = 30 * (i >> 3) + modPrms[ci]
			s = p * p - 7
			p8 = p << 3
			for j in range(8):
				c = s // 30 * 8 + ndxs[s % 30]
				buf[c::p8] = [False] * ((lmtbf - c) // p8 + 1)
				s += p * gaps[ci]
				ci += 1
	for i in range(lmtbf - 6 + ndxs[(limit - 7) % 30]):
		if buf[i]:
			yield (30 * (i >> 3) + modPrms[i & 7])
for t in range(int(input())):
	N = int(input())
	A = [1, 1, 1, 1]
	for i in range(4, N + 1):
		A.append(A[i - 1] + A[i - 4])
	print(len(list(primes235(A[N]))))


def findPrimes(primes, n):
	if len(primes) < n + 1:
		primes = primes + [1 for i in range(len(primes), n + 1)]
		num = int(n ** 0.5)
		primes[0] = primes[1] = 0
		for i in range(2, num + 1):
			if primes[i] == 1:
				for j in range(2 * i, n + 1, i):
					primes[j] = 0
	return primes

def findWays(wayList, n):
	next_index = len(wayList)
	while next_index <= n:
		wayList.append(wayList[next_index - 1] + wayList[next_index - 4])
		next_index += 1
	else:
		return wayList[n]
T = int(input())
wList = [1, 1, 1, 1]
primes = [0, 0]
for i in range(T):
	N = int(input())
	ways = findWays(wList, N)
	primes = findPrimes(primes, ways)
	P = primes[:ways + 1].count(1)
	print(P)


def walls(laid, height):
	if laid > height:
		return 0
	if laid == height:
		return 1
	return walls(laid + 1, height) + walls(laid + 4, height)

def primes_less_than(M):
	sieve = [True] * (M + 1)
	sieve[0] = sieve[1] = False
	prime = 2
	while prime ** 2 <= M:
		if sieve[prime]:
			for i in range(prime ** 2, M + 1, prime):
				sieve[i] = False
		prime += 1
	return len([i for i in range(2, M + 1) if sieve[i]])
T = int(input())
for i in range(T):
	N = int(input())
	arrangements = walls(0, N)
	print(primes_less_than(arrangements))


import itertools

def erat2():
	D = {}
	yield 2
	for q in itertools.islice(itertools.count(3), 0, None, 2):
		p = D.pop(q, None)
		if p is None:
			D[q * q] = q
			yield q
		else:
			x = p + q
			while x in D or not x & 1:
				x += p
			D[x] = p

def get_primes_erat(n):
	return list(itertools.takewhile(lambda p: p < n, erat2()))

def numberofways(N):
	if N < 4:
		return 1
	return numberofways(N - 1) + numberofways(N - 4)
for case in range(int(input())):
	N = int(input())
	print(len(get_primes_erat(numberofways(N) + 1)))


T = int(input())

def primes(n):
	ls = [True] * n
	limit = int(n ** 0.5) + 1
	for i in range(2, limit):
		if ls[i]:
			(j, k) = (i ** 2, 1)
			while j < n:
				ls[j] = False
				j = i ** 2 + k * i
				k += 1
	return sum([a for a in ls[2:] if a])
for t in range(T):
	N = int(input())
	if N < 4:
		print(0)
		continue
	dp = [0] * (N + 1)
	for i in range(4):
		dp[i] = 1
	for i in range(4, N + 1):
		dp[i] = dp[i - 1] + dp[i - 4]
	print(primes(dp[N] + 1))


import sys
n = int(input())
ts = []
for i in range(n):
	ts.append(int(input()))
maxt = max(ts)
ms = [1, 1, 1, 2]
for i in range(4, maxt):
	ms.append(ms[i - 1] + ms[i - 4])
maxm = ms[-1]
isprime = [True] * (maxm - 1)
i = 2
while i <= maxm:
	if not isprime[i - 2]:
		i = i + 1
		continue
	j = i + i
	while j <= maxm:
		isprime[j - 2] = False
		j += i
	i = i + 1
ps = [0]
for a in isprime:
	if a:
		ps.append(ps[-1] + 1)
	else:
		ps.append(ps[-1])
for t in ts:
	print(ps[ms[t - 1] - 1])


import math

def Cnk(n, k):
	if k > n:
		return 0
	if k > n - k:
		k = n - k
	res = 1
	for i in range(0, k):
		res *= n - i
		res //= i + 1
	return res

def isPrime(n):
	sqrtn = math.sqrt(n)
	for i in prime_table:
		if i > sqrtn:
			break
		if n % i == 0:
			return False
	return True

def getprime(n):
	numb = prime_table[-1]
	if n < numb:
		a = 0
		b = len(prime_table)
		while b - a > 1:
			c = (b + a) // 2
			if prime_table[c] <= n:
				a = c
			else:
				b = c
		return a + 1
	numb += 2
	while numb <= n:
		if isPrime(numb):
			prime_table.append(numb)
		numb += 2
	return len(prime_table)
prime_table = [2, 3, 5, 7, 11, 13, 17, 19]
t = int(input())
for case_t in range(t):
	n = int(input())
	count = 1
	rem = n % 4
	div = n // 4
	for i in range(1, div + 1):
		count += Cnk(i + rem + 4 * (div - i), i)
	if count == 1:
		print(0)
	else:
		print(getprime(count))


import math

def factorial(num):
	total = 1
	for i in range(1, num + 1):
		total *= i
	return total

def product(num):
	total = 1
	for i in num:
		total *= i
	return total

def combinations(top, bottom1, bottom2):
	if top == 1:
		return 1
	if bottom1 + bottom2 > top:
		return -1
	top_list = list(range(1, top + 1))
	bottom = max(bottom1, bottom2)
	for i in range(bottom):
		if top_list[i] == i + 1:
			top_list[i] = 1
	loner = product(top_list) / factorial(min(bottom1, bottom2))
	return loner

def sieve(num):
	if num < 2:
		return 0
	primes = [1] * num
	primes[0] = 0
	primes[1] = 0
	for i in range(4, len(primes), 2):
		primes[i] = 0
	multiplier = 3
	while multiplier < math.ceil(math.sqrt(num)):
		for i in range(2, math.ceil(num / multiplier)):
			primes[multiplier * i] = 0
		multiplier += 1
	num_primes = 0
	for i in primes:
		if i == 1:
			num_primes += 1
	return num_primes
cases = int(input())
for i in range(cases):
	case = int(input())
	s = 1
	for i in range(1, int(case / 4) + 1):
		s += combinations(case + i - i * 4, i, case - i * 4)
	print(sieve(int(s) + 1))


def findConfig(N, configs):
	if len(configs) == 0:
		configs.append(0)
		configs.append(1)
		configs.append(1)
		configs.append(1)
		configs.append(2)
		index = 5
	else:
		index = len(configs)
	for i in range(index, N + 1):
		numWays = configs[i - 4] + configs[i - 1]
		configs.append(numWays)
	return configs[N]

def populatePrimes(N, primes, base):
	if len(primes) < N + 1:
		for i in range(len(primes), N + 1):
			primes.append(True)
		while base <= N // 2:
			value = base * 2
			while value <= N:
				primes[value] = False
				value += base
			base += 1
	return primes
numInputs = int(input())
configs = []
primes = []
base = 2
for i in range(numInputs):
	N = int(input())
	numConfigs = findConfig(N, configs)
	populatePrimes(numConfigs, primes, base)
	count = 0
	for i in range(2, numConfigs + 1):
		if primes[i]:
			count += 1
	print(count)


import sys

def numConfigs(n):
	if n < 0:
		return 0
	if n == 1 or n == 0:
		return 1
	return numConfigs(n - 1) + numConfigs(n - 4)

def numPrimes(n):
	numPrimes = 0
	for i in range(2, n + 1):
		foundPrime = False
		j = 2
		while j * j <= i and (not foundPrime):
			if i % j == 0:
				foundPrime = True
			j += 1
		if not foundPrime:
			numPrimes += 1
	return numPrimes
numCases = int(sys.stdin.readline().strip())
for i in range(numCases):
	bricks = int(sys.stdin.readline().strip())
	configs = numConfigs(bricks)
	print(numPrimes(configs))


def get_input():
	T = int(input())
	Ns = []
	for t in range(T):
		Ns.append(int(input()))
	return Ns

def n_choose_k(n, k):
	from math import factorial
	return factorial(n) / (factorial(k) * factorial(n - k))

def get_possibilities(N):
	sum = 0
	from math import floor
	for k in range(floor(N / 4) + 1):
		sum += n_choose_k(N - k * 4 + k, k)
	return int(sum)

def get_rid_of_multiples(sieve, base, N):
	mult = 2
	while base * mult <= N:
		if mult * base in sieve:
			sieve.remove(mult * base)
		mult += 1

def get_primes(N):
	sieve = set(range(2, N + 1))
	composites_exist = True
	for i in range(2, N + 1):
		if i in sieve:
			get_rid_of_multiples(sieve, i, N)
	return len(sieve)

def solve(Ns):
	for N in Ns:
		print(get_primes(get_possibilities(N)))
solve(get_input())


def sieve(n):
	if n < 3:
		return []
	s = list(range(n // 2))
	for i in s:
		if i:
			k = i - ~i
			for j in range(k * k, n, 2 * k):
				s[j // 2] = 0
	primes = [2]
	primes += [2 * s[prime] + 1 for prime in range(len(s)) if s[prime] > 0]
	return primes

def f(n):
	if n < 4:
		return 1
	else:
		return f(n - 1) + f(n - 4)
for t in [1] * int(input()):
	countWays = f(int(input()))
	siev = sieve(countWays + 1)
	print(len(siev))


def countprimes3(x):
	if x == 1:
		return []
	else:
		a = [False, False] + [True for i in range(2, x + 1)]
		i = 2
		while i <= x ** 0.5:
			if a[i] is True:
				k = 0
				while i ** 2 + k * i <= x:
					a[i ** 2 + k * i] = False
					k += 1
			i += 1
		return a

def bricks(n):
	if n in range(0, 4):
		return 1
	else:
		return bricks(n - 1) + bricks(n - 4)
i = int(input())
for _ in range(i):
	j = int(input())
	z = bricks(j)
	print(countprimes3(z).count(True))


from math import sqrt, factorial

def search_brickspace(width):
	fours = width // 4
	if fours == 0:
		return 1
	return 1 + int(sum((factorial(width - i * 3) / (factorial(i) * factorial(width - i * 4)) for i in range(1, fours + 1))))

def is_prime(n):
	if n < 2:
		return False
	if n == 2:
		return True
	if n & 1 == 0:
		return False
	for i in range(3, int(sqrt(n)) + 1, 2):
		if n % i == 0:
			return False
	return True

def primes_in(end):
	return sum((1 if is_prime(i) else 0 for i in range(end + 1)))
T = int(input())
N = [int(input()) for _ in range(T)]
for n in N:
	configurations = search_brickspace(n)
	print(primes_in(configurations))


import math

def sieve_of_eratosthenes(n):
	num_list = list(range(n + 1))
	num_list[1] = 0
	prime_list = []
	i = 2
	while i * i <= n:
		for j in range(i * i, len(num_list), i):
			num_list[j] = 0
		i += 1
	for x in num_list:
		if x != 0:
			prime_list.append(x)
	print(len(prime_list))

def mysteriosos(n):
	n_times = n // 4
	s = 0
	for i in range(n_times + 1):
		bricks4 = i
		bricks1 = n - i * 4
		s += math.factorial(bricks4 + bricks1) / (math.factorial(bricks4) * math.factorial(bricks1))
	if s < 4:
		print(int(s) - 1)
	else:
		sieve_of_eratosthenes(int(s))
tests = int(input())
for _ in range(tests):
	mysteriosos(int(input()))


from math import factorial

def comb(n):
	hb = n // 4
	total = 1
	for x in range(1, hb + 1):
		vb = n - x * 4
		total += factorial(x + vb) / (factorial(x) * factorial(vb))
	return int(total)

def rwh_primes(n):
	sieve = [True] * n
	for i in range(3, int(n ** 0.5) + 1, 2):
		if sieve[i]:
			sieve[i * i::2 * i] = [False] * int((n - i * i - 1) / (2 * i) + 1)
	result = []
	if n > 2:
		result.append(2)
	return result + [i for i in range(3, n, 2) if sieve[i]]
num_tests = int(input())
samples = []
for n in range(num_tests):
	samples.append(int(input()))
for n in samples:
	c = comb(n)
	print(len(rwh_primes(c + 1)))


from math import factorial

def countPrimesUnder(n):
	if n <= 1:
		return 0
	n = int(n) + 1
	sieve = [True] * n
	for i in range(3, int(n ** 0.5) + 1, 2):
		if sieve[i]:
			sieve[i * i::2 * i] = [False] * ((n - i * i - 1) // (2 * i) + 1)
	myPrimes = [2] + [i for i in range(3, n, 2) if sieve[i]]
	return len(myPrimes)

def countPerms(x, y):
	return int(factorial(x + y) / (factorial(x) * factorial(y)))
for i in range(0, int(input())):
	lengthWall = int(input())
	num1by4 = 0
	numPermutations = 0
	while lengthWall >= num1by4:
		numPermutations += countPerms(lengthWall - num1by4, num1by4 // 4)
		num1by4 += 4
	print(countPrimesUnder(numPermutations))


values = []
values.append(1)
for i in range(1, 41):
	value = values[i - 1]
	if i - 4 >= 0:
		value = value + values[i - 4]
	values.append(value)
primes = [True] * (values[-1] + 1)
primes[0] = False
primes[1] = False
for i in range(2, len(primes)):
	if primes[i]:
		for j in range(i * i, len(primes), i):
			primes[j] = False
primes_count = [0] * (values[-1] + 1)
for i in range(1, len(primes)):
	primes_count[i] = primes_count[i - 1]
	if primes[i]:
		primes_count[i] = primes_count[i] + 1
test_count = int(input())
for i in range(0, test_count):
	print(primes_count[values[int(input())]])


def confs(n):
	if n < 4:
		return 1
	elif n == 4:
		return 2
	else:
		return confs(n - 1) + confs(n - 4)

def sieve(m):
	arr = [1] * m
	arr[0] = arr[1] = 0
	primes = 0
	for i in range(2, m):
		if arr[i] == 1:
			primes += 1
			for j in range(i * 2, m, i):
				arr[j] = 0
	return primes
for _ in range(int(input())):
	n = int(input())
	m = confs(n)
	p = sieve(m + 1)
	print(p)


def is_prime(n):
	if n <= 3:
		return n >= 2
	if n % 2 == 0 or n % 3 == 0:
		return False
	for i in range(5, int(n ** 0.5) + 1, 6):
		if n % i == 0 or n % (i + 2) == 0:
			return False
	return True

def nCr(n, r):
	res = 1.0
	for i in range(1, r + 1):
		res *= (n + 1 - i) / i
	return res

def calc(n):
	fours = int(n / 4)
	res = 1.0
	for i in range(1, fours + 1):
		res += nCr(n - i * 4 + i, i)
	if res < 2:
		return 0
	p = 1
	for i in range(1, int(res - 2), 2):
		p += 1 if is_prime(i + 2) else 0
	p += 1 if res % 2 != 0 and is_prime(res) else 0
	return p
for i in range(int(input())):
	print(calc(int(input())))


from math import ceil
from bisect import bisect
arrange = {i: 1 for i in range(4)}
for i in range(4, 41):
	arrange[i] = arrange[i - 1] + arrange[i - 4]

def numWallArrangements(n):
	return arrange[n]
s = set([i for i in range(2, 218000)])
for i in range(2, 468):
	s = set(filter(lambda x: x % i != 0 or i == x, s))

def numPrimesToN(n):
	print(bisect(sorted(s), n))
T = int(input())
for i in range(T):
	arrangements = numWallArrangements(int(input()))
	numPrimesToN(arrangements)


def is_prime(n):
	if n <= 3:
		return n >= 2
	if n % 2 == 0 or n % 3 == 0:
		return False
	for i in range(5, int(n ** 0.5) + 1, 6):
		if n % i == 0 or n % (i + 2) == 0:
			return False
	return True

def way_of_bricks(n):
	count = 1
	for big_brick in range(1, n // 4 + 1):
		count += combination(n - 3 * big_brick, big_brick)
	return count

def combination(n, k):
	from math import factorial
	return int(factorial(n) / factorial(k) / factorial(n - k))
t = int(input())
layouts = way_of_bricks(40)
primes = [False] * (layouts + 1)
for i in range(layouts + 1):
	if is_prime(i):
		primes[i] = True
for i in range(t):
	n = int(input())
	layouts = way_of_bricks(n)
	print(primes[:layouts + 1].count(True))


def primes(x):
	ar = [True] * (x + 1)
	ar[0] = False
	ar[1] = False
	for i in range(2, int(x ** (1 / 2)) + 1):
		if ar[i] == True:
			for j in range(2 * i, x + 1, i):
				ar[j] = False
	return ar.count(True)
t = int(input())
for _ in range(t):
	n = int(input())
	ar = [0] * (n + 1)
	ar[0] = 1
	for i in range(1, n + 1):
		if i - 1 >= 0:
			ar[i] += ar[i - 1]
		if i - 4 >= 0:
			ar[i] += ar[i - 4]
	print(primes(ar[n]))


import math

def count_combinations(n):
	table = [-1] * (n + 1)
	for i in range(n + 1):
		if i < 4:
			table[i] = 1
		else:
			table[i] = table[i - 1] + table[i - 4]
	return table[n]

def count_primes(m):
	if m == 1:
		return 0
	root_m = math.ceil(math.sqrt(m))
	num_odds = math.ceil(m / 2)
	primes = [True] * (num_odds + 1)
	primes[0] = False
	result = num_odds
	i = 3
	while i <= root_m:
		if primes[i // 2]:
			j = 3
			while j * i <= m:
				temp = j * i // 2
				if primes[temp]:
					primes[j * i // 2] = False
					result -= 1
				j += 2
		i += 2
	return result

def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		print(count_primes(count_combinations(n)))
main()


import os, sys, itertools
for _ in range(int(input())):
	N = int(input())
	if N > 6:
		ways = [[0] * (N + 1) for _ in range(N + 1)]
		ways[0][1] = 1
		ways[1][2] = 1
		ways[2][3] = 1
		ways[3][0] = 1
		ways[3][4] = 1
		for i in range(4, N):
			ways[i][0] = sum(ways[i - 4])
			ways[i][i + 1] = 1
			for j in range(1, i + 1):
				ways[i][j] = ways[i - j][0]
		wn = sum(ways[N - 1])
	else:
		wn = max(N - 2, 1)
	primes = [1] * (wn + 1)
	for i in range(2, wn + 1):
		if primes[i] == 1:
			for j in range(2 * i, wn + 1, i):
				primes[j] = 0
	print(sum(primes) - 2)


import sys

def main():
	numinputs = int(input())
	dp = [1, 1, 1, 1]
	inputs = [int(val) for val in sys.stdin]
	for i in range(4, 41):
		dp.append(dp[i - 1] + dp[i - 4])
	n = max(dp)
	primes = find_primes(n + 1)
	primes = count_primes(primes, n + 1)
	for x in inputs:
		print(primes[dp[x]])

def find_primes(n):
	primes = [val for val in range(2, n + 1)]
	primes = [0, 0] + primes
	i = 2
	while i * i <= n:
		for j in range(2 * i, n + 1, i):
			primes[j] = 0
		for temp in range(i + 1, n + 1):
			if primes[temp] != 0:
				i = temp
				break
	return primes

def count_primes(primes, n):
	count = 0
	for i in range(n + 1):
		if primes[i] != 0:
			count += 1
		primes[i] = count
	return primes
main()


case_count = int(input())
cases = [int(input()) for _ in range(case_count)]

def prime_number_count(maximum):
	prime_count = 0
	vec = [True for _ in range(maximum + 1)]
	for i in range(2, maximum + 1):
		if vec[i]:
			prime_count += 1
			for j in range(2, maximum + 1):
				if i * j > maximum:
					break
				vec[i * j] = False
	return prime_count
for case in cases:
	solution_count = [0 for _ in range(case + 1)]
	solution_count[0] = 1
	for i in range(1, case + 1):
		if i >= 4:
			solution_count[i] = solution_count[i - 1] + solution_count[i - 4]
		else:
			solution_count[i] = solution_count[i - 1]
	final_count = solution_count[case]
	print(prime_number_count(final_count))


def isprime(n):
	if n == 1:
		return False
	for i in range(2, int(n ** 0.5 + 1)):
		if n % i == 0:
			return False
	return True

def calprime(n):
	c = 0
	for i in range(2, n + 1):
		if isprime(i):
			c = c + 1
	return c

def calno(n):
	a = [1, 1, 1, 1]
	for i in range(4, n + 1):
		a.append(a[i - 1] + a[i - 4])
	return calprime(a[n])
t = int(input())
ar = []
for i in range(t):
	ar.append(int(input()))
for i in range(t):
	print(calno(ar[i]))


res = [1] * 4
for i in range(4, 41):
	res.append(res[-1] + res[-4])
mx = res[-1]
l = [False] * 2 + [True] * (mx - 1)
z = [False] * (mx // 2)
for i in range(2, int(mx ** 0.5) + 1):
	if l[i]:
		l[i * i::i] = z[:mx // i - i + 1]
for i in range(int(input())):
	print(sum(l[:res[int(input())] + 1]))


import math
mlist = []
plist = []
nplist = []

def isPrime(num):
	if plist[num] != -1:
		return plist[num]
	elif num == 1:
		plist[num] = 0
		return plist[num]
	else:
		status = True
		for i in range(2, int(math.sqrt(num) + 1)):
			if num % i == 0:
				status = False
		plist[num] = 1 if status else 0
		return plist[num]

def countPrime(num):
	if nplist[num] != -1:
		return nplist[num]
	elif num == 1:
		nplist[num] = 0
		return nplist[num]
	else:
		nplist[num] = countPrime(num - 1) + isPrime(num)
		return nplist[num]

def computeM(N):
	if mlist[N] != -1:
		pass
	elif N == 1:
		mlist[N] = 1
	else:
		n4 = N // 4
		s = 0
		for i in range(0, n4 + 1):
			p = math.factorial(N - 3 * i) / math.factorial(N - 4 * i) / math.factorial(i)
			s += int(p)
		mlist[N] = s
	return mlist[N]

def preprocess(num):
	for i in range(1, num + 1):
		countPrime(i)
	return countPrime(num)
T = int(input())
mlist = [-1 for i in range(41)]
plist = [-1 for i in range(10000000)]
nplist = [-1 for i in range(10000000)]
for i in range(T):
	N = int(input())
	M = computeM(N)
	P = preprocess(M)
	print(P)


_MAX_VALUE = 250000

def _is_prime(n):
	if n <= 3:
		return n >= 2
	if n % 2 == 0 or n % 3 == 0:
		return False
	for i in range(5, int(n ** 0.5) + 1, 6):
		if n % i == 0 or n % (i + 2) == 0:
			return False
	return True

def _calc_primes(_MAX_VALUE):
	nprimes = [0 for _ in range(_MAX_VALUE)]
	for i in range(1, _MAX_VALUE):
		nprimes[i] = nprimes[i - 1] + _is_prime(i)
	return nprimes

def _num_combinations(n):
	variants = [0 for _ in range(n + 1)]
	for i in range(n + 1):
		if i == 0:
			continue
		elif i == 5:
			break
		variants[i] = 1
	for i in range(4, n + 1):
		variants[i] += variants[i - 1] + variants[i - 4]
	return variants[-1]

def num_primes(n, primes):
	return primes[_num_combinations(n)]
primes = _calc_primes(_MAX_VALUE)
t = int(input())
for _ in range(t):
	n = int(input())
	print(num_primes(n, primes))


import math

def sieve(m):
	is_prime = [True] * (m + 1)
	is_prime[0] = is_prime[1] = False
	for i in range(2, math.ceil(math.sqrt(m)) + 1):
		if is_prime[i]:
			for multiple in range(i * i, m + 1, i):
				is_prime[multiple] = False
	return is_prime
tests = int(input())
for i in range(tests):
	n = int(input())
	divide = n // 4
	m = 0
	a = 0
	if n == 1 or n == 2 or n == 3:
		print(0)
	else:
		for i in range(1, divide + 1):
			a += math.factorial(n - 4 * i + i) // (math.factorial(i) * math.factorial(n - 4 * i))
		m = 1 + a
		count1 = 0
		is_prime = sieve(m)
		print(sum(is_prime))


import math

def is_prime(n):
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			return False
	return True

def cnt_prime(n):
	ret = 0
	for i in range(2, n + 1):
		if is_prime(i):
			ret += 1
	return ret

def nCr(n, r):
	ret = 1
	for _ in range(r):
		ret *= n
		n -= 1
	dev = 1
	for i in range(1, r + 1):
		dev *= i
	return int(ret / dev)

def f(n):
	ret = 1
	for i in range(1, int(n / 4) + 1):
		r = n - i * 4
		wn = i + r
		add = nCr(wn, r)
		ret += add
	return ret
t = int(input())
for _ in range(t):
	n = int(input())
	pn = f(n)
	print(cnt_prime(pn))


def nchoosek(n, k):
	p = 1
	for i in range(k):
		p = p * (n - i) // (i + 1)
	return p

def countm(n):
	s = 0
	for nh in range(n // 4 + 1):
		nv = n - 4 * nh
		s += nchoosek(nh + nv, nh)
	return s

def genIsPrime(pmax):
	pend = pmax + 1
	is_prime = pend * [True]
	is_prime[0] = is_prime[1] = False
	for i in range(2, pend):
		if is_prime[i]:
			for j in range(i * i, pend, i):
				is_prime[j] = False
	return is_prime
t = int(input())
for _ in range(t):
	n = int(input())
	m = countm(n)
	print(sum(genIsPrime(m)))


T = int(input())
for _ in range(T):
	N = int(input())
	DP = [1] * (N + 1)
	for i in range(4, N + 1):
		DP[i] = DP[i - 1] + DP[i - 4]
	Num = DP[N]
	sieve = [True] * (Num + 1)
	p = 2
	primes = 0
	while p <= Num:
		primes += 1
		for k in range(p + p, Num + 1, p):
			sieve[k] = False
		p += 1
		while p <= Num and (not sieve[p]):
			p += 1
	print(primes)


import math
f = math.factorial
primes = [1] * 217287
root = int(math.sqrt(217286))
for i in range(2, root + 2):
	j = 2
	while i * j <= 217286:
		primes[i * j] = 0
		j += 1
t = int(input())
while t > 0:
	n = int(input())
	s = n // 4
	total = 1
	for i in range(1, s + 1):
		single = n - i * 4
		total += f(i + single) / f(i) / f(single)
	j = 2
	count = 0
	while j <= total:
		if primes[j] == 1:
			count += 1
		j += 1
	print(count)
	t -= 1


ans = [0, 0, 0, 0, 1, 2, 2, 3, 4, 4, 6, 8, 9, 11, 15, 19, 24, 32, 42, 53, 68, 91, 119, 155, 204, 269, 354, 462, 615, 816, 1077, 1432, 1912, 2543, 3385, 4522, 6048, 8078, 10794, 14475, 19385]
ncases = int(input())
for _ in range(ncases):
	print(ans[int(input())])


from math import sqrt

def main():
	testcases = range(int(input()))
	for testcase in testcases:
		length = int(input())
		total_arrangements = arrangements(length)
		total_primes = count_primes(total_arrangements)
		print(total_primes)

def arrangements(length):
	count = (1, 1, 1, 2, 3, 4, 5, 7, 10, 14, 19, 26, 36, 50, 69, 95, 131, 181, 250, 345, 476, 657, 907, 1252, 1728, 2385, 3292, 4544, 6272, 8657, 11949, 16493, 22765, 31422, 43371, 59864, 82629, 114051, 157422, 217286)
	assert length <= 40
	return count[length - 1]

def count_primes(stop, cache=[0]):
	total = cache[-1]
	for number in range(len(cache), stop + 1):
		total += is_prime(number)
		cache.append(total)
	return cache[stop]

def is_prime(number):
	if number < 2:
		return False
	elif number == 2:
		return True
	elif number % 2 == 0:
		return False
	stop = int(sqrt(number)) + 1
	for test in range(3, stop, 2):
		if number % test == 0:
			return False
	return True
main()


def main():
	import math
	factorial = [1]
	for i in range(1, 41):
		factorial.append(factorial[i - 1] * i)
	for _ in range(int(input())):
		N = int(input())
		m = 1
		for i in range(1, N // 4 + 1):
			m += factorial[N - 3 * i] // (factorial[i] * factorial[N - 4 * i])
		s = [1] * (m + 1)
		s[0] = 0
		s[1] = 0
		p = 0
		for i in range(2, m + 1):
			if s[i]:
				p += 1
				for j in range(2 * i, m + 1, i):
					s[j] = 0
		print(p)
main()


def main():
	import math
	factorial = [1]
	for i in range(1, 41):
		factorial.append(factorial[i - 1] * i)
	for _ in range(int(input())):
		N = int(input())
		m = 1
		for i in range(1, N // 4 + 1):
			m += factorial[N - 3 * i] // (factorial[i] * factorial[N - 4 * i])
		s = [1] * (m + 1)
		s[0] = 0
		s[1] = 0
		p = 0
		for i in range(2, m + 1):
			if s[i]:
				p += 1
				for j in range(2 * i, m + 1, i):
					s[j] = 0
		print(p)
main()


import math
arr = [0] * 41
arr[0] = arr[1] = arr[2] = arr[3] = 1
for i in range(4, 41):
	arr[i] = arr[i - 1] + arr[i - 4]
isprime = [True] * 217287
for j in range(4, 217287, 2):
	isprime[j] = False
for j in range(6, 217287, 3):
	isprime[j] = False
for j in range(3, math.ceil(math.sqrt(217287)) + 1, 2):
	i = j
	while i * j < 217287:
		isprime[i * j] = False
		i += 1
count = [0] * 217287
count[0] = count[1] = 0
for i in range(2, 217287):
	count[i] = count[i - 1]
	if isprime[i]:
		count[i] += 1
t = int(input())
for i in range(t):
	n = int(input())
	print(count[arr[n]])


def memoize(func):
	pool = {}

	def wrapper(*arg):
		if arg not in pool:
			pool[arg] = func(*arg)
		return pool[arg]
	return wrapper

def get_primes(max):
	sieve = [True] * max
	sieve[0] = False
	sieve[1] = False
	for i in range(int(max ** 0.5)):
		if sieve[i]:
			for composite in range(i * i, max, i):
				sieve[composite] = False
	return [index for (index, is_prime) in enumerate(sieve) if is_prime]
primes = get_primes(217286 + 1)
T = int(input())
for cases in range(T):
	N = int(input())

	@memoize
	def get_ways(n):
		if n < 0:
			return 0
		elif n == 0:
			return 1
		else:
			return get_ways(n - 1) + get_ways(n - 4)
	print(sum((1 for i in primes if i <= get_ways(N))))


import math
T = {1: 1, 2: 1, 3: 1, 4: 2}
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, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]

def isprime(n):
	if n in primes:
		return True
	elif n not in primes and n < primes[-1]:
		return False
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			return False
	primes.append(n)
	return True

def num_primes(n):
	primes = 0
	if n <= 1:
		return 0
	for i in range(2, n + 1):
		if isprime(i):
			primes += 1
	return primes
D = {16493: 1912, 22765: 2543, 31422: 3385, 43371: 4522, 59864: 6048, 82629: 8078, 114051: 10794, 157422: 14475, 217286: 19385, 8675: 1077, 11949: 1432}

def wall(n):
	if n < 5:
		return num_primes(T[n])
	i = 5
	while i != n + 1:
		T[i] = T[i - 1] + T[i - 4]
		i += 1
	if T[n] in D:
		return D[T[n]]
	return num_primes(T[n])
num_trials = int(input())
for i in range(num_trials):
	k = int(input())
	print(wall(k))


import fileinput
memoBricks = {0: 0, 1: 1, 2: 1, 3: 1, 4: 2}
memoPrimes = {0: 0, 1: 0}

def isPrime(n):
	if n == 2 or n == 3:
		return True
	elif n < 2 or n % 2 == 0:
		return False
	elif n < 9:
		return True
	elif n % 3 == 0:
		return False
	next = int(n ** 0.5)
	start = 5
	while start <= next:
		if n % start == 0:
			return False
		if n % (start + 2) == 0:
			return False
		start += 6
	return True

def getNumOrderings(n):
	if n in memoBricks:
		return memoBricks[n]
	for i in range(5, n + 1):
		memoBricks[i] = memoBricks[i - 1] + memoBricks[i - 4]
	return memoBricks[n]

def getNumPrimes(n):
	if n in memoPrimes:
		return memoPrimes[n]
	for i in range(1, n + 1):
		memoPrimes[i] = memoPrimes[i - 1]
		if isPrime(i):
			memoPrimes[i] = memoPrimes[i] + 1
	return memoPrimes[n]
first = True
for line in fileinput.input():
	if not first:
		numOrderings = getNumOrderings(int(line))
		print(getNumPrimes(numOrderings))
	else:
		first = False


import math

def brick_combos(n):
	if n == 0:
		return 0
	hori = int(n / 4)
	verti = n % 4
	count_permu = 0
	while hori > 0:
		count_permu += int(math.factorial(hori + verti) / math.factorial(hori) / math.factorial(verti))
		hori -= 1
		verti += 4
	return count_permu + 1

def isPrime(n):
	if n == 1:
		return 0
	else:
		squareRoot = int(math.sqrt(n))
		for i in range(2, squareRoot + 1):
			if n % i == 0:
				return 0
		return 1

def PL(n):
	prime_less = 0
	for i in range(2, n + 1):
		if isPrime(i):
			prime_less += 1
	return prime_less

def main():
	test_cases = int(input())
	for i in range(test_cases):
		n = int(input())
		combos = brick_combos(n)
		print(PL(combos))
	return 0
main()


import sys
C = 4

def generate_primes(n):
	if n == 2:
		return [2]
	elif n < 2:
		return []
	sieve = list(range(3, n + 1, 2))
	root_n = n ** 0.5
	mid = (n + 1) // 2 - 1
	i = 0
	m = 3
	while m <= root_n:
		if sieve[i]:
			j = (m * m - 3) // 2
			sieve[j] = 0
			while j < mid:
				sieve[j] = 0
				j += m
		i += 1
		m = 2 * i + 3
	return [2] + [p for p in sieve if p]

def choose(n, k):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p *= n
			q *= i
			n -= 1
		return p // q
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	(count, n) = (1, 1)
	if N % C == 0:
		count += 1
	while N - n * C > 0:
		count += choose(N - (C - 1) * n, n)
		n += 1
	print(len(generate_primes(count)))


def is_prime(n):
	if n <= 3:
		return True
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True
li = [0] * 50
li[0] = 1
li[1] = 1
li[2] = 1
li[3] = 1
li[4] = 2
li[5] = 3
for i in range(6, 50):
	li[i] = li[i - 1] + li[i - 4]
t = int(input())
for _ in range(t):
	n = int(input())
	cnt = li[n]
	ans = 0
	for i in range(2, cnt + 1):
		if is_prime(i):
			ans += 1
	print(ans)


import sys
C = 4

def generate_primes(n):
	if n == 2:
		return [2]
	elif n < 2:
		return []
	sieve = list(range(3, n + 1, 2))
	root_n = n ** 0.5
	mid = (n + 1) // 2 - 1
	i = 0
	m = 3
	while m <= root_n:
		if sieve[i]:
			j = (m * m - 3) // 2
			sieve[j] = 0
			while j < mid:
				sieve[j] = 0
				j += m
		i += 1
		m = 2 * i + 3
	return [2] + [p for p in sieve if p]

def choose(n, k):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p *= n
			q *= i
			n -= 1
		return p // q
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	(count, n) = (1, 1)
	if N % C == 0:
		count += 1
	while N - n * C > 0:
		count += choose(N - (C - 1) * n, n)
		n += 1
	print(len(generate_primes(count)))


__author__ = 'said'

def numberOfP(m):
	counter = 0
	zahlen = [True] * (m + 1)
	zahlen[0] = False
	zahlen[1] = False
	p = 2
	while p * p <= m:
		if zahlen[p] == True:
			for k in range(p * p, m + 1, p):
				zahlen[k] = False
		p = p + 1
	for (i, v) in enumerate(zahlen):
		if v == True:
			counter += 1
	return counter

def possibilities(n):
	if n < 4:
		return 1
	else:
		sum = 1
		for j in range(0, n - 3):
			sum += possibilities(n - (j + 4))
		return sum
numberofInputIntegers = int(input())
for w in range(0, numberofInputIntegers):
	m = possibilities(int(input()))
	print(numberOfP(m))


dp = [1] + [0] * 43
for i in range(40):
	dp[i + 1] += dp[i]
	dp[i + 4] += dp[i]
sieve = [1] * (dp[40] * 2)
primes = []
for i in range(2, len(sieve)):
	if sieve[i]:
		primes.append(i)
		for j in range(2, dp[40] * 2 // i):
			sieve[i * j] = 0
primes.append(1000000000)
for _ in range(int(input().strip())):
	N = dp[int(input().strip())]
	i = 0
	while N >= primes[i]:
		i += 1
	print(i)


import math

def nCr(n, r):
	f = math.factorial
	return f(n) // f(r) // f(n - r)

def get_ways_to_lay_bricks(n):
	ways_to_lay = 1
	max_possible_groups_of_4 = n // 4
	for i in range(1, max_possible_groups_of_4 + 1):
		singles = n - 4 * i
		groups_of_4 = i
		ways_to_lay += nCr(singles + groups_of_4, singles)
	return ways_to_lay

def get_count_of_primes_up_to(m):
	if m < 2:
		return 0
	primes = [False, False] + [True] * (m - 1)
	prime_count = 1
	current_index = 2
	while current_index <= m:
		for i in range(current_index * 2, m + 1, current_index):
			primes[i] = False
		true_encountered = False
		for i in range(current_index + 1, m + 1, 1):
			if primes[i] == True:
				current_index = i
				true_encountered = True
				prime_count += 1
				break
		if not true_encountered:
			break
	return prime_count

def process_test_cases():
	t = eval(input())
	for i in range(t):
		n = eval(input())
		m = get_ways_to_lay_bricks(n)
		print(get_count_of_primes_up_to(m))
process_test_cases()


import sys
C = 4

def generate_primes(n):
	if n == 2:
		return [2]
	elif n < 2:
		return []
	sieve = list(range(3, n + 1, 2))
	root_n = n ** 0.5
	mid = (n + 1) // 2 - 1
	i = 0
	m = 3
	while m <= root_n:
		if sieve[i]:
			j = (m * m - 3) // 2
			sieve[j] = 0
			while j < mid:
				sieve[j] = 0
				j += m
		i += 1
		m = 2 * i + 3
	return [2] + [p for p in sieve if p]

def choose(n, k):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p *= n
			q *= i
			n -= 1
		return p // q
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	(count, n) = (1, 1)
	if N % C == 0:
		count += 1
	while N - n * C > 0:
		count += choose(N - (C - 1) * n, n)
		n += 1
	print(len(generate_primes(count)))


from bisect import bisect_right

def isPrime(x):
	if x < 2:
		return False
	i = 2
	while i * i <= x:
		if x % i == 0:
			return False
		i += 1
	return True
T = [0 for _ in range(41)]
P = [2]
T[0] = 1
T[1] = 1
T[2] = 1
T[3] = 1
for i in range(4, 41):
	T[i] = T[i - 1] + T[i - 4]
t = int(input())
for _ in range(t):
	n = int(input())
	p = T[n]
	if P[-1] < p:
		i = P[-1] + 1
		while i <= p:
			if isPrime(i):
				P.append(i)
			i += 1
	print(bisect_right(P, p))


dp = [0, 0, 0, 0, 1, 2, 2, 3, 4, 4, 6, 8, 9, 11, 15, 19, 24, 32, 42, 53, 68, 91, 119, 155, 204, 269, 354, 462, 615, 816, 1077, 1432, 1912, 2543, 3385, 4522, 6048, 8078, 10794, 14475, 19385]
T = int(input())
for i in range(0, T):
	N = int(input())
	print(dp[N])


arr = [0] * (40 + 1)
arr[0] = 1
for i in range(1, 40 + 1):
	arr[i] = arr[i - 1]
	if i >= 4:
		arr[i] += arr[i - 4]
MAX = 217286
prime = [True] * (MAX + 1)
prime[0] = False
prime[1] = False
count = [0] * (MAX + 1)
for i in range(2, MAX + 1):
	count[i] = count[i - 1]
	if prime[i]:
		count[i] += 1
		t = 2
		while t * i <= MAX:
			prime[t * i] = False
			t += 1
t = eval(input())
while t > 0:
	t -= 1
	print(count[arr[eval(input())]])


def primes(n):
	if n <= 2:
		return 0
	sieve = [True] * n
	for i in range(3, int(n ** 0.5) + 1, 2):
		if sieve[i]:
			sieve[i * i::2 * i] = [False] * int((n - i * i - 1) / (2 * i) + 1)
	return len([i for i in range(3, n, 2) if sieve[i]]) + 1

def find_configs(N):
	if N == 0:
		return 1
	elif N < 0:
		return 0
	return find_configs(N - 1) + find_configs(N - 4)
T = int(input())
for i in range(T):
	print(primes(find_configs(int(input())) + 1))


def isPrime(n):
	if n % 2 == 0:
		return False
	i = 3
	while i * i <= n:
		if n % i == 0:
			return False
		i += 2
	return True

def primes(n):
	if n == 1:
		return 0
	i = 3
	cnt = 1
	while i <= n:
		if isPrime(i):
			cnt += 1
		i += 2
	return cnt

def pascal_triangle(n):
	pascal = []
	pascal.append([1, 0])
	for i in range(1, n + 1):
		pascal.append([])
		pascal[i] = [0] * (i + 2)
		pascal[i][0] = 1
		for j in range(1, i + 1):
			pascal[i][j] = pascal[i - 1][j] + pascal[i - 1][j - 1]
	return pascal

def combs(n, pascal):
	c = 1
	segs = n // 4
	for i in range(1, segs + 1):
		c += pascal[n - i * 4 + i][i]
	return c
pascal = pascal_triangle(40)
for test in range(int(input().strip())):
	N = int(input().strip())
	print(primes(combs(N, pascal)))


import math

def solve(n):
	totalNumber = 0
	for x in range(int(n / 4) + 1):
		totalNumber += comb(n - x * 3, x)
	return sieve(int(totalNumber))

def sieve(n):
	primes = []
	checked = set([])
	for x in range(2, n + 1):
		if x not in checked:
			primes.append(x)
			for t in range(x, n + 1, x):
				checked.add(t)
	return len(primes)

def comb(n, r):
	return math.factorial(n) / (math.factorial(r) * math.factorial(n - r))
t = int(input())
for x in range(t):
	print(solve(int(input())))


from collections import defaultdict

def calculate(N):
	memo = defaultdict(int)
	for i in range(4):
		memo[i] = 1
	for i in range(4, N + 1):
		memo[i] = memo[i - 1] + memo[i - 4]
	return memo[N]

def primes_up_to(N):
	if N <= 1:
		return 0
	primes = [True for _ in range(N + 1)]
	for i in range(3, N, 2):
		for j in range(i + i, N + 1, i):
			primes[j] = False
	return len([p for p in primes[3::2] if p]) + 1
for testcase in range(int(input())):
	N = int(input())
	num_ways = calculate(N)
	num_primes = primes_up_to(num_ways)
	print(num_primes)