Read problems statements in [Hindi], [Mandarin Chinese], [Russian], [Vietnamese], and [Bengali] as well.

A tuple $(a, b, c)$ is considered good if it consists of three prime numbers $a$, $b$ and $c$ such that $a < b < c ≤ N$ and $a + b = c$.

Two tuples are considered different if they differ in at least one position. Given $N$, find the number of good tuples that can be formed by integers from $1$ to $N$.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The following $T$ lines contain a single integer $N$.

------  Output ------
For each test case, print a single line containing one integer — the number of good tuples which can be formed using integers from $1$ to $N$.

------  Constraints ------
$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{6}$

----- Sample Input 1 ------ 
2

3

6
----- Sample Output 1 ------ 
0

1
----- explanation 1 ------ 
Example case 1: There are no good tuples. $(1, 2, 3)$ is not a good tuple since $1$ is not prime.

Example case 2: $(2, 3, 5)$ is a good tuple since $2$, $3$ and $5$ are prime and $2 + 3 = 5$.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Number theory

Dynamic programming

Mathematics


Solutions:
import bisect
primes = {2}
primes = [False, False] + [True] * 10 ** 6
p = 2
dp = []
while p * p <= 10 ** 6:
	if primes[p] == True:
		for i in range(2 * p, 10 ** 6, p):
			primes[i] = False
	p += 1
for i in range(2, i):
	if primes[i] and primes[i - 2]:
		dp.append(i)
for _ in range(int(input())):
	print(bisect.bisect_right(dp, int(input())))


e = 10 ** 6 + 1
sieve = [1] * e
sieve[0] = sieve[1] = 0
for i in range(2, e):
	for j in range(i * i, e, i):
		sieve[j] = 0
dp = [0] * e
for i in range(2, e):
	dp[i] += dp[i - 1]
	if sieve[i] and sieve[i - 2]:
		dp[i] += 1
t = int(input())
for _ in range(t):
	n = int(input())
	print(dp[n])


def get_seive(n):
	seive = [0] * (n + 1)
	seive[0] = 1
	seive[1] = 1
	for i in range(2, n):
		if seive[i] != 0:
			continue
		for j in range(2, n // i + 1):
			seive[i * j] += 1
	primes = []
	for i in range(n + 1):
		if seive[i] == 0:
			primes.append(i)
	return (seive, primes)

def get_dp(seive, primes, n):
	dp = [0] * (n + 1)
	for p in primes:
		if 2 + p <= n and seive[2 + p] == 0:
			dp[2 + p] = 1
	sdp = [0] * (n + 1)
	for i in range(1, n + 1):
		sdp[i] = sdp[i - 1] + dp[i]
	return sdp
(SEIVE, PRIMES) = get_seive(1000007)
DP = get_dp(SEIVE, PRIMES, 1000007)
t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	print(DP[n])


def Solve(n, ans):
	primeL = [True for i in range(n + 1)]
	primeL[0] = False
	primeL[1] = False
	p = 2
	while p * p <= n:
		if primeL[p] == True:
			for i in range(p * p, n + 1, p):
				primeL[i] = False
		p += 1
	for i in range(n + 1):
		if primeL[i] and primeL[i - 2]:
			ans[i] = ans[i - 1] + 1
		else:
			ans[i] = ans[i - 1]
	return ans
ans = [0] * 1000001
L = Solve(1000000, ans)
for _ in range(int(input())):
	print(L[int(input())])


N = 10 ** 6
dp = [0] * (N + 1)
dp[0] = 1
dp[1] = 1
for i in range(2, 1001):
	if dp[i] == 0:
		j = i * i
		while j <= N:
			dp[j] = 1
			j = j + i
pre = [0] * (N + 1)
for i in range(2, N + 1):
	pre[i] = pre[i - 1]
	if dp[i] == 0 and dp[i - 2] == 0:
		pre[i] = pre[i] + 1
t = int(input())
for i in range(t):
	n = int(input())
	print(pre[n])


prime = [True for i in range(1000000 + 1)]
(prime[0], prime[1]) = (False, False)
p = 2
while p * p <= 1000000:
	if prime[p] == True:
		for i in range(p * p, 1000000 + 1, p):
			prime[i] = False
	p += 1
arr = [0] * 1000001
cnt = 0
for i in range(5, 1000001):
	if prime[i] and prime[i - 2]:
		cnt += 1
	arr[i] = cnt
t = int(input())
for h in range(t):
	n = int(input())
	print(arr[n])


import math

def SieveOfEratosthenes(num):
	prime = [True for i in range(num + 1)]
	p = 2
	while p * p <= num:
		if prime[p] == True:
			for i in range(p * p, num + 1, p):
				prime[i] = False
		p += 1
	return prime

def preprocess_dp(N):
	primes = SieveOfEratosthenes(N)
	dp = [0 for i in range(N + 1)]
	for i in range(5, N + 1):
		dp[i] = dp[i - 1]
		if primes[i] and primes[i - 2]:
			dp[i] = dp[i] + 1
	return dp
dp = preprocess_dp(1000000)
for _ in range(int(input())):
	N = int(input())
	print(dp[N])


import math

def sieveOfEratosthenes(n):
	primes = [0, 0] + [1] * (n - 1)
	p = 2
	while p ** 2 <= n:
		if primes[p]:
			for i in range(p ** 2, n + 1, p):
				primes[i] = 0
		p += 1
	return primes

def precompute():
	MAX = 10 ** 6
	ans = {}
	primes = sieveOfEratosthenes(MAX)
	c = 0
	for i in range(2, MAX + 1):
		if primes[i] and primes[i - 2]:
			c += 1
		ans[i] = c
	return ans
ans = precompute()
for T in range(int(input())):
	n = int(input())
	print(ans[n])


N = [None] * (10 ** 6 + 1)
for i in range(2, len(N)):
	if N[i] == None:
		N[i] = 1
		for i in range(2 * i, len(N), i):
			N[i] = 0
ans = [0] * (10 ** 6 + 1)
ans1 = 0
for i in range(3, 10 ** 6 + 1, 1):
	if N[i] and N[i - 2]:
		ans1 += 1
	ans[i - 1] = ans1
T = int(input())
for _ in range(T):
	n = int(input())
	print(ans[n - 1])


k = 1000000
a = []
ans = [0] * (k + 1)

def SieveOfEratosthenes(n, ans):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	for i in range(5, k + 1):
		if prime[i]:
			if prime[i - 2]:
				ans[i] = ans[i - 1] + 1
			else:
				ans[i] = ans[i - 1]
		else:
			ans[i] = ans[i - 1]
SieveOfEratosthenes(k, ans)
t = int(input())
while t:
	t -= 1
	n = int(input())
	print(ans[n])


def snek(n):
	s = [1 for i in range(n + 1)]
	p = 2
	s[0] = 0
	s[1] = 0
	while p * p <= n:
		if s[p] == 1:
			j = 2
			for i in range(p * j, n + 1, p):
				s[i] = 0
				j += 1
		p += 1
	l = []
	for i in range(2, n + 1):
		if s[i]:
			l.append(i)
	return s
x = 1000000
res = snek(x)
c = 0
l = [0] * 1000001
l[0] = 0
l[1] = 0
for i in range(2, x + 1):
	if res[i] == 1 and res[i - 2] == 1 and (i - (i - 2) == 2):
		c += 1
	l[i] = c
t = int(input())
for i in range(t):
	n = int(input())
	print(l[n])


def SieveOfEratosthenes(n):
	prime = [1 for i in range(n + 1)]
	p = 2
	prime[0] = 0
	prime[1] = 0
	while p * p <= n:
		if prime[p] == 1:
			j = 2
			for i in range(p * j, n + 1, p):
				prime[i] = 0
				j += 1
		p += 1
	l = []
	for i in range(2, n + 1):
		if prime[i]:
			l.append(i)
	return prime
X = 1000000
res = SieveOfEratosthenes(X)
c = 0
l = [0] * 1000001
l[0] = 0
l[1] = 0
for i in range(2, X + 1):
	if res[i] == 1 and res[i - 2] == 1 and (i - (i - 2) == 2):
		c += 1
	l[i] = c
for i in range(int(input())):
	print(l[int(input())])


primes = [1] * (10 ** 6 + 1)
primes[0] = primes[1] = 0
for i in range(2, 10 ** 6 + 1):
	if primes[i] == 1:
		x = 2
		while x * i < 10 ** 6 + 1:
			primes[i * x] = 0
			x += 1
ans = [0] * (10 ** 6 + 1)
s = 1
for i in range(2, 10 ** 6 + 1):
	if primes[i] == 1 and primes[i - 2] == 1:
		ans[i] = s
		s += 1
	else:
		ans[i] = s
for _ in range(int(input())):
	x = int(input())
	print(ans[x] - 1)


prime_rn = 1000001
prime = [True] * prime_rn
prime[0] = prime[1] = False
for i in range(2, 10 ** 6 + 1):
	if prime[i] == 1:
		y = 2
		while y * i < 10 ** 6 + 1:
			prime[i * y] = 0
			y += 1
ans = [0] * 1000001
string = 1
for i in range(2, 10 ** 6 + 1):
	if prime[i] == 1 and prime[i - 2] == 1:
		ans[i] = string
		string += 1
	else:
		ans[i] = string
T = int(input())
for j in range(T):
	N = int(input())
	print(ans[N] - 1)


Prange = 10 ** 6 + 1
prime = [True] * Prange
count = [0] * Prange
prime[0] = prime[1] = False
for i in range(2, int(Prange / 2) + 1):
	if prime[i]:
		for j in range(i * 2, Prange, i):
			prime[j] = False
for i in range(2, Prange):
	if prime[i] and prime[i - 2]:
		count[i] = count[i - 1] + 1
	else:
		count[i] = count[i - 1]
T = int(input())
for id in range(T):
	N = int(input())
	print(count[N])


l = [True] * 1000001
ans = [0] * 1000001
l[0] = l[1] = False
for i in range(2, 500001):
	if l[i]:
		for j in range(i + i, 1000001, i):
			l[j] = False
ans[0] = ans[1] = 0
for i in range(2, 1000001):
	if l[i] and l[i - 2]:
		ans[i] = ans[i - 1] + 1
	else:
		ans[i] = ans[i - 1]
T = int(input())
for tc in range(T):
	N = int(input())
	print(ans[N])


l = 10 ** 6 + 1
is_prime = [True] * l
count = [0] * l
is_prime[0] = is_prime[1] = False
for i in range(2, int(l / 2) + 1):
	if is_prime[i]:
		for j in range(i * 2, l, i):
			is_prime[j] = False
for i in range(2, l):
	if is_prime[i] and is_prime[i - 2]:
		count[i] = count[i - 1] + 1
	else:
		count[i] = count[i - 1]
T = int(input())
for tc in range(T):
	N = int(input())
	print(count[N])


n = 1000000 + 1
ans = []
for j in range(n + 1):
	ans.append(0)
prime = [True for i in range(n + 1)]
p = 2
while p * p <= n:
	if prime[p] == True:
		for i in range(p * p, n + 1, p):
			prime[i] = False
	p += 1
for p in range(5, n + 1):
	if prime[p]:
		if prime[p - 2]:
			ans[p] = ans[p - 1] + 1
		else:
			ans[p] = ans[p - 1]
	else:
		ans[p] = ans[p - 1]
t = int(input())
for i in range(t):
	a = int(input())
	print(ans[a])


from re import L
import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
sys.setrecursionlimit(100000000)
inp = lambda : int(input())
strng = lambda : input().strip()
jn = lambda x, l: x.join(map(str, l))
strl = lambda : list(input().strip())
mul = lambda : map(int, input().strip().split())
mulf = lambda : map(float, input().strip().split())
seq = lambda : list(map(int, input().strip().split()))
ceil = lambda x: int(x) if x == int(x) else int(x) + 1
ceildiv = lambda x, d: x // d if x % d == 0 else x // d + 1
flush = lambda : stdout.flush()
stdstr = lambda : stdin.readline()
stdint = lambda : int(stdin.readline())
stdpr = lambda x: stdout.write(str(x))
prime = [True for i in range(10 ** 6 + 1)]

def SieveOfEratosthenes(n):
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
SieveOfEratosthenes(10 ** 6)
count = 0
a = [0] * (10 ** 6 + 1)
for i in range(5, 10 ** 6 + 1):
	if prime[i - 2] and prime[i]:
		count += 1
	a[i] = count
t = int(input())
for i in range(t):
	n = inp()
	print(a[n])


v = [1] * 1000001
ans = [0] * 1000001
v[0] = 0
v[1] = 0
p = []
for i in range(2, 500001):
	if v[i] == 1:
		p.append(i)
		for j in range(i + i, 1000001, i):
			v[j] = 0
ans[0] = ans[1] = 0
for i in range(2, 1000001):
	if v[i] > 0 and v[i - 2] > 0:
		ans[i] = ans[i - 1] + 1
	else:
		ans[i] = ans[i - 1]
T = int(input())
for tc in range(T):
	N = int(input())
	print(ans[N])


tests = int(input())
mx = 10 ** 6 + 1
primes = [0, 0] + [1] * mx
for i in range(2, int(mx ** 0.5) + 1):
	if primes[i]:
		for j in range(i ** 2, mx, i):
			primes[j] = 0
count = 0
a = [0] * mx
for i in range(mx):
	if primes[i - 2] and primes[i]:
		count += 1
	a[i] = count
for t in range(tests):
	N = int(input())
	print(a[N])


t = int(input())
l = [True] * 1000001
l[0] = False
l[1] = False
ans = [0] * 1000001
for i in range(2, int(1000001 ** 0.5) + 1):
	if l[i] == True:
		for j in range(i * i, 1000001, i):
			l[j] = False
count = 0
for i in range(5, 1000001):
	if l[i] and l[i - 2]:
		count = count + 1
	ans[i] = count
for _ in range(t):
	n = int(input())
	print(ans[n])


try:
	n = 1000000
	t = int(input())
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p ** 2, n + 1, p):
				prime[i] = False
		p += 1
	prime[0] = False
	prime[1] = False
	prime_set = []
	last_prime = 2
	for x in range(n + 1):
		if prime[x]:
			last_prime = x
			prime_set.append(x)
		else:
			prime_set.append(last_prime)
	result_set = []
	count = 0
	for (i, el) in enumerate(prime_set[:-1]):
		if el + 2 == prime_set[i + 1]:
			count += 1
		result_set.append(count)
	for _ in range(t):
		n = int(input())
		print(result_set[n - 1])
except Exception:
	pass


import bisect
from functools import lru_cache
import sys
from bisect import bisect_right
import math
from collections import Counter, deque
mod = 10 ** 9 + 7
inf = float('inf')
sieve_limit = 10 ** 6

def arrInt():
	return list(map(int, input().split()))

def generateSieve():
	primes = []
	arr = [1] * (sieve_limit + 1)
	arr[0] = 0
	arr[1] = 0
	for i in range(2, sieve_limit + 1):
		if arr[i] == 0:
			continue
		primes.append(i)
		j = i * i
		while j <= sieve_limit:
			arr[j] = 0
			j += i
	return primes
primes = generateSieve()
ans_arr = [0] * len(primes)
counter = Counter()
for i in range(1, len(primes)):
	ans_arr[i] = counter[primes[i] - 2] + ans_arr[i - 1]
	counter[primes[i]] += 1
TESTING = False
if TESTING:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
else:
	input = sys.stdin.readline
T = int(input())
for _ in range(T):
	n = int(input())
	m = bisect.bisect_right(primes, n)
	print(ans_arr[m - 1])


primes = [True] * 1000001
primes[0] = False
primes[1] = False
for i in range(2, 1001):
	if primes[i]:
		for j in range(i * i, 1000001, i):
			primes[j] = False
ans = [0] * 1000001
for i in range(2, 1000001):
	if primes[i] and primes[i - 2]:
		ans[i] = ans[i - 1] + 1
	else:
		ans[i] = ans[i - 1]
tc = int(input())
for _ in range(tc):
	n = int(input())
	print(ans[n])


def prime(n, final):
	arr = [True for i in range(n + 1)]
	p = 2
	arr[0] = False
	arr[1] = False
	while p * p <= n:
		if arr[p] == True:
			for i in range(p * 2, n + 1, p):
				arr[i] = False
		p += 1
	for i in range(2, n + 1):
		if arr[i] == True and arr[i - 2] == True:
			final[i] = final[i - 1] + 1
		else:
			final[i] = final[i - 1]
final = [0 for i in range(1000001)]
prime(1000000, final)
for _ in range(int(input())):
	print(final[int(input())])


prime = [1] * 1000001
(prime[0], prime[1]) = (0, 0)
for i in range(2, 1000001):
	if prime[i] == 1:
		for j in range(i * i, 1000001, i):
			prime[j] = 0
ans = [0, 0]
cur = 0
for i in range(2, len(prime)):
	if prime[i] and prime[i - 2]:
		cur += 1
	ans.append(cur)
t = int(input())
for _ in range(t):
	n = int(input())
	print(ans[n])


def some(n):
	my_babys = [True] * (n + 1)
	p = 2
	while p * p <= n:
		if my_babys:
			for i in range(p * p, n + 1, p):
				my_babys[i] = False
		p += 1
	ans = [0] * (n + 1)
	c = 0
	for i in range(5, n + 1):
		if my_babys[i] and my_babys[i - 2]:
			c += 1
		ans[i] = c
	return ans
ans = some(10 ** 6)
for _ in range(int(input())):
	n = int(input())
	print(ans[n])


t = int(input())

def soe(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p]:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	ans = [0 for i in range(n + 1)]
	c = 0
	for i in range(5, n + 1):
		if prime[i] and prime[i - 2]:
			c += 1
		ans[i] = c
	return ans
ans = soe(10 ** 6)
for i in range(t):
	n = int(input())
	print(ans[n])


arr = [0] * (10 ** 6 + 1)

def seive(n=10 ** 6 + 1):
	prime = [True] * n
	(prime[0], prime[1]) = (False, False)
	p = 2
	while p * p <= n:
		if prime[p]:
			for i in range(p * p, n, p):
				prime[i] = False
		p += 1
	for i in range(2, n):
		if prime[i] and prime[i - 2]:
			arr[i] += arr[i - 1] + 1
		else:
			arr[i] = arr[i - 1]
seive()
for _ in range(int(input())):
	print(arr[int(input())])


from math import sqrt
from bisect import bisect

def sieve(n):
	k = sqrt(n)
	d = list(range(n + 1))
	p = []
	i = 2
	if n == 1:
		return []
	while d[i] <= k:
		if d[i] != 0:
			for j in range(i * i, n + 1, i):
				d[j] = 0
			p.append(i)
		i += 1
	return [i for i in range(3, n + 1) if d[i] != 0]
primes = sieve(10 ** 6)
plimit = len(primes)
prectpl = []
for i in range(1, plimit):
	if primes[i] - primes[i - 1] == 2:
		prectpl.append(primes[i])
for _ in range(int(input())):
	n = int(input())
	print(bisect(prectpl, n))


def isprime(n):
	if n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i += 6
	return True

def sol():
	p = [0, 0, 0, 0, 0, 1, 1, 2, 2]
	prev = True
	count = 2
	for i in range(9, 10 ** 6 + 2, 2):
		if isprime(i):
			if prev:
				count += 1
			prev = True
		else:
			prev = False
		p.extend([count, count])
	return p
good = sol()
for t in range(int(input())):
	print(good[int(input())])


import sys
sys.setrecursionlimit(10 ** 5 + 1)
inf = int(10 ** 20)
max_val = inf
min_val = -inf
RW = lambda : sys.stdin.readline().strip()
RI = lambda : int(RW())
RMI = lambda : [int(x) for x in sys.stdin.readline().strip().split()]
RWI = lambda : [x for x in sys.stdin.readline().strip().split()]

def Sieve(N):
	primes = [True] * (N + 1)
	primes[0] = False
	primes[1] = False
	i = 2
	while i * i < N:
		if primes[i]:
			for j in range(i * i, N + 1, i):
				primes[j] = False
		i += 1
	cnt = [0] * (N + 1)
	for i in range(2, N + 1):
		cnt[i] = cnt[i - 1]
		if primes[i] and primes[i - 2]:
			cnt[i] += 1
	return cnt
cnt = Sieve(1000005)
for _ in range(RI()):
	N = RI()
	print(cnt[int(N)])


from collections import defaultdict
ans = defaultdict(lambda : 0)

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	(prime[0], prime[1]) = (False, False)
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	count = 0
	for i in range(2, n + 1):
		if prime[i - 2] and prime[i]:
			count += 1
		ans[i] = count
SieveOfEratosthenes(10 ** 6 + 10)
for i in range(int(input())):
	n = int(input())
	print(ans[n])


def Prime(n):
	if n & 1 == 0:
		return False
	d = 3
	while d * d <= n:
		if n % d == 0:
			return False
		d = d + 2
	return True
ans = []
for i in range(1000002):
	ans.append(0)
for i in range(5, 1000001):
	if Prime(i - 2) and Prime(i):
		ans[i] = ans[i - 1] + 1
	else:
		ans[i] = ans[i - 1]
t = int(input())
while t:
	n = int(input())
	print(ans[n])
	t -= 1


ans = set()

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	c = 0
	for p in range(2, n):
		if prime[p]:
			ans.add(p)
SieveOfEratosthenes(1000001)
ansf = [0] * 1000006
c = 0
for i in range(5, 1000001):
	if i in ans and i - 2 in ans:
		c += 1
	ansf[i] = c
for _ in range(int(input())):
	n = int(input())
	print(ansf[n - 1])


l = [True] * 1000001
(l[0], l[1]) = (False, False)
for i in range(2, 1000):
	if l[i] == True:
		for j in range(i * i, 1000001, i):
			l[j] = False
l1 = [0] * 1000001
for i in range(5, 1000001):
	if l[i] and l[i - 2]:
		l1[i] = l1[i - 1] + 1
	else:
		l1[i] = l1[i - 1]
for _ in range(int(input())):
	n = int(input())
	print(l1[n])


prime = [True] * 1000001
prime[0] = prime[1] = False
for num in range(2, 1000):
	for x in range(num * num, 1000001, num):
		prime[x] = False
answer = [0] * 1000001
for i in range(5, 1000001):
	if prime[i] and prime[i - 2]:
		answer[i] = answer[i - 1] + 1
	else:
		answer[i] = answer[i - 1]
printAns = []
for _ in range(int(input())):
	N = printAns.append(answer[int(input())])
for x in printAns:
	print(x)


RANGE = 10 ** 6 + 1
sieve = [True] * RANGE
sieve[1] = False
sieve[0] = False
for i in range(2, RANGE):
	if sieve[i]:
		j = 2
		while i * j < RANGE:
			sieve[i * j] = False
			j += 1
candidate = [0] * RANGE
for i in range(2, RANGE):
	if sieve[i] and sieve[i - 2]:
		candidate[i] = 1
for i in range(1, RANGE):
	candidate[i] += candidate[i - 1]
for __ in range(int(input())):
	n = int(input())
	print(candidate[n])


t = int(input())
n = 10 ** 6 + 5
temp = {i: True for i in range(2, n)}
temp[1] = False
ls = [0, 0, 0, 0, 0]
for i in range(2, n):
	if temp[i]:
		j = i * 2
		while j <= n:
			temp[j] = False
			j += i
for i in range(5, n):
	if temp[i] and temp[i - 2]:
		ls.append(ls[i - 1] + 1)
	else:
		ls.append(ls[i - 1])
for i in range(t):
	s = int(input())
	print(ls[s])


n = int(1000000.0) + 1
prime = [0] * n
i = 2
while i * i < n:
	if prime[i] == 0:
		j = 2
		while j * i < n:
			prime[i * j] = 1
			j += 1
	i += 1
prime_lis = [x for x in range(2, n) if prime[x] == 0]
len_prime = len(prime_lis)
ans = [0] * n
for i in range(len_prime - 1):
	if prime_lis[i] + 2 < n and prime[prime_lis[i] + 2] == 0:
		ans[prime_lis[i] + 2] += 1
for i in range(1, n):
	ans[i] += ans[i - 1]
for _ in range(int(input())):
	N = int(input())
	print(ans[N])


def sieve():
	n = 1000000
	prime = [True for i in range(n + 1)]
	pList = [0 for i in range(n + 1)]
	i = 3
	last_prime = 3
	count = 0
	while i <= n:
		if prime[i] == True:
			if i - last_prime == 2:
				count += 1
			last_prime = i
			pList[i] = count
			if i != n:
				pList[i + 1] = count
			j = i * i
			while j <= n:
				prime[j] = False
				j += i
		else:
			pList[i] = pList[i - 2]
			pList[i + 1] = pList[i - 2]
		i += 2
	return pList
primes = sieve()
for _ in range(0, int(input())):
	n = int(input())
	print(primes[n])


isprime = [True] * (10 ** 6 + 5)
isprime[0] = isprime[1] = False
primes = []
ans = [0] * (10 ** 6 + 5)
for i in range(2, 10 ** 6 + 5):
	if isprime[i]:
		primes.append(i)
		j = i + i
		while j < 10 ** 6 + 5:
			isprime[j] = False
			j += i
	ans[i] = ans[i - 1]
	if isprime[i] and isprime[i - 2]:
		ans[i] += 1
for _ in range(int(input())):
	n = int(input())
	print(ans[n])


a = 10 ** 6 + 1
IsPrime = [True] * a
IsPrime[0] = False
IsPrime[1] = False
PrimeNumbers = []
for i in range(2, a):
	if IsPrime[i]:
		PrimeNumbers.append(i)
		for j in range(i * i, a, i):
			IsPrime[j] = False
ans = [0] * a
for i in range(2, a):
	if IsPrime[i] and IsPrime[i - 2]:
		ans[i] = ans[i - 1] + 1
	else:
		ans[i] = ans[i - 1]
n = int(input())
for _ in range(n):
	m = int(input())
	print(ans[m])


import math
n = 1000005
l = [1 for _ in range(n + 1)]
(l[0], l[1]) = (0, 0)
ans = [0 for _ in range(n + 1)]
(ans[0], ans[1]) = (0, 0)
for i in range(2, math.ceil(math.sqrt(n))):
	if l[i] != 0:
		for j in range(i * i, n + 1, i):
			l[j] = 0
for i in range(2, n + 1):
	if l[i] == 1 and l[i - 2] == 1:
		ans[i] = ans[i - 1] + 1
	else:
		ans[i] = ans[i - 1]
for _ in range(int(input())):
	n = int(input())
	print(ans[n])


def calculate(n):
	return ans[n]

def prime_number(prime, ans):
	for i in range(2, 10 ** 6 + 1):
		if prime[i]:
			for j in range(2, 10 ** 6):
				if i * j > 10 ** 6:
					break
				prime[i * j] = False
		ans[i] = ans[i - 1]
		if prime[i] == True and prime[i - 2] == True:
			ans[i] += 1
prime = [True] * (10 ** 6 + 1)
prime[0] = False
prime[1] = False
ans = [0] * (10 ** 6 + 1)
prime_number(prime, ans)
T = int(input())
while T:
	n = int(input())
	print(calculate(n))
	T -= 1


prime = [True for i in range(1000001)]
p = 2
while p * p <= 1000000:
	if prime[p] == True:
		for i in range(p * p, 1000001, p):
			prime[i] = False
	p += 1
ans = [0] * 1000001
for i in range(5, 1000001):
	if prime[i] and prime[i - 2]:
		ans[i] = ans[i - 1] + 1
	else:
		ans[i] = ans[i - 1]
for _ in range(int(input())):
	n = int(input())
	print(ans[n])


n = 1000007
prime = [True] * (n + 1)
prime[0] = False
prime[1] = False
for p in range(2, n + 1):
	if prime[p] == True:
		for i in range(p * p, n + 1, p):
			prime[i] = False
a = [0] * (n + 1)
for i in range(2, n + 1):
	if prime[i] and prime[i - 2]:
		a[i] = a[i - 1] + 1
	else:
		a[i] = a[i - 1]
for _ in range(int(input())):
	n = int(input())
	print(a[n])


n = 10 ** 6
prime = [1 for i in range(n + 1)]
i = 2
while i * i <= n:
	if prime[i] == 1:
		for j in range(i * i, n + 1, i):
			prime[j] = 0
	i += 1
prime[0] = 0
prime[1] = 0
tuples = [0 for i in range(n + 1)]
for i in range(2, n + 1):
	if prime[i] == 1 and prime[i - 2] == 1:
		tuples[i] = tuples[i - 1] + 1
	else:
		tuples[i] = tuples[i - 1]
for _ in range(int(input())):
	n = int(input())
	count = tuples[n]
	print(count)


s = set()

def Ssss(x):
	pr = [True for i in range(x + 1)]
	p = 2
	while p * p <= x:
		if pr[p] == True:
			for i in range(p * 2, x + 1, p):
				pr[i] = False
		p += 1
	pr[0] = False
	pr[1] = False
	for p in range(x + 1):
		if pr[p]:
			s.add(p)
Ssss(1000001)
arrr = [0] * 10000000
count = 0
for z in range(5, 1000001):
	if z in s and z - 2 in s:
		count += 1
		arrr[z] = count
	else:
		arrr[z] = count
for _ in range(int(input())):
	n = int(input())
	print(arrr[n])


def primes(n):
	is_prime = [True] * (n + 1)
	is_prime[0] = False
	is_prime[1] = False
	for i in range(2, n + 1):
		if is_prime[i] and i * i <= n:
			for j in range(i * i, n, i):
				is_prime[j] = False
	pairs = [0] * (n + 1)
	count = 0
	pairs[3] = 1
	pairs[4] = 1
	for i in range(5, len(pairs)):
		if is_prime[i] and is_prime[i - 2]:
			count += 1
		pairs[i] = count
	return pairs
t = int(input())
nums = []
for _ in range(t):
	n = int(input())
	nums.append(n)
biggest = max(nums)
pairs = primes(biggest)
for i in range(t):
	n = nums[i]
	if n < 5:
		print(0)
		continue
	print(pairs[n])


def sieve(n, choice):
	ans = (n + 1) * [True]
	for i in range(2, int(n ** 0.5) + 1):
		if ans[i]:
			for j in range(2 * i, n + 1, i):
				ans[j] = False
	if choice:
		return ans
	res = []
	for i in range(2, n + 1):
		if ans[i]:
			res.append(i)
	return res
s = sieve(10 ** 6, True)
ans = 5 * [0]
for i in range(5, 10 ** 6 + 1):
	if s[i] and s[i - 2]:
		ans.append(ans[-1] + 1)
	else:
		ans.append(ans[-1])
for _ in range(int(input())):
	n = int(input())
	print(ans[n])


import math
t = int(input())
a = [0] * 1000001
prime = [2, 3]
first = 3
second = 0
count = 0
for j in range(5, 1000001, 2):
	flag = False
	for k in prime:
		if j % k == 0:
			flag = True
			break
		if k > math.sqrt(j):
			break
	if not flag:
		second = j
		if second - first == 2:
			count += 1
		first = j
		prime.append(j)
	a[j] = count
	a[j + 1] = count
for i in range(t):
	num = int(input())
	print(a[num])


import math
ar = [1] * 1000002

def fg(n):
	k = 2
	while k < n + 1:
		if ar[k] == 1:
			for j in range(k * k, n + 1, k):
				ar[j] = 0
		k += 1
ns = [0] * 1000002

def gh():
	k = 0
	for i in range(5, 1000001):
		if ar[i] == 1 and ar[i - 2] == 1:
			k += 1
		ns[i] = k
fg(1000001)
gh()
for _ in range(int(input())):
	n = int(input())
	print(ns[n])


import sys
sys.setrecursionlimit(10 ** 7)

def I():
	return int(sys.stdin.readline().rstrip())

def MI():
	return map(int, sys.stdin.readline().rstrip().split())

def LI():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def LI2():
	return list(map(int, sys.stdin.readline().rstrip()))

def S():
	return sys.stdin.readline().rstrip()

def LS():
	return list(sys.stdin.readline().rstrip().split())

def LS2():
	return list(sys.stdin.readline().rstrip())

def T():
	return tuple(map(int, sys.stdin.readline().rstrip().split()))

def sieve(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * 2, n + 1, p):
				prime[i] = False
		p += 1
	prime[0] = False
	prime[1] = False
	return prime
maxN = int(10000000.0) + 5
prime = sieve(maxN)
ans = [0] * (maxN + 1)
for i in range(1, maxN + 1):
	ans[i] = ans[i - 1] + (prime[i] and prime[i - 2])
for _ in range(I()):
	n = I()
	print(ans[n])


import math
mx = 10 ** 6 + 1
pr = [1] * mx
pr[0] = 0
pr[1] = 0
for i in range(2, int(math.sqrt(mx)) + 1):
	if pr[i]:
		for j in range(i * i, mx, i):
			pr[j] = 0
count = 0
ans = [0, 0, 0, 0]
for i in range(4, mx):
	if pr[i] and pr[i - 2]:
		count += 1
	ans.append(count)
for _ in range(int(input().strip())):
	n = int(input().strip())
	print(ans[n])


def sievePrime(N):
	prime = [True for i in range(N + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * 2, N + 1, p):
				prime[i] = False
		p += 1
	prime[0] = False
	prime[1] = False
	return prime
n = 1000000 + 1
pr = sievePrime(n)
ans = []
for i in range(n + 1):
	ans.append(0)
for i in range(5, n + 1):
	if pr[i]:
		if pr[i - 2]:
			ans[i] = ans[i - 1] + 1
		else:
			ans[i] = ans[i - 1]
	else:
		ans[i] = ans[i - 1]
for _ in range(int(input())):
	n = int(input())
	print(ans[n])


def seive(b):
	b += 1
	pr = [True] * b
	ret = []
	pr[0] = pr[1] = False
	for i in range(2, b):
		if pr[i]:
			for j in range(i * i, b, i):
				pr[j] = False
			if pr[i - 2]:
				ret.append(i)
	return ret
from bisect import bisect_left

def solve():
	x = int(input())
	return bisect_left(pr, x + 1)
pr = seive(10 ** 6)
for i in range(int(input())):
	print(solve())


def binSearch(a, k):
	n = len(a)
	(l, u) = (0, n - 1)
	while l <= u:
		mid = (l + u) // 2
		if a[mid] == k:
			return mid + 1
		if a[mid] > k:
			u = mid - 1
		else:
			l = mid + 1
	return u + 1
tc = int(input())
q = []
for t in range(tc):
	q.append(int(input()))
n = max(q)
sieve = [True for _ in range(n + 1)]
sieve[1] = False
for i in range(2, int(n ** 0.5) + 1):
	if sieve[i] == False:
		continue
	for j in range(2 * i, n + 1, i):
		sieve[j] = False
pp = []
for i in range(2, n - 1):
	if sieve[i] and sieve[i + 2]:
		pp.append(i + 2)
for n in q:
	print(binSearch(pp, n))