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

You are given all $N - 1$ integers in the range $[2, N]$. In each step, you choose $2$ distinct integers and if they share a common factor greater than $1$, you combine them into the same group. You keep doing it until no further merging is possible.

Belonging to a group is an equivalence relation. So if integers $a$ and $b$ are in the same group and integers $b$ and $c$ are in the same group, then integers $a$ and $c$ are also said to be in the same group.

Find the total number of groups formed in the end.

------ Input ------

First line will contain $T$, number of test cases. Then the test cases follow. 
Each test case contains a single line of input, a single integer $N$. 

------ Output ------
For each test case, output in a single line the answer to the problem.

------ Constraints  ------
$1 ≤ T ≤ 2\cdot 10^{5}$
$2 ≤ N ≤ 10^{7}$

------  Subtasks ------
Subtask #1 (30 points): 
$1 ≤ T ≤ 200$
$2 ≤ N ≤ 1000$

Subtask #2 (70 points): original constraints

----- Sample Input 1 ------ 
3

2

4

8
----- Sample Output 1 ------ 
1

2

3
----- explanation 1 ------ 
Test Case $1$: The final group is $\{2\}$.

Test Case $2$: The final groups are $\{2, 4\}$, and $\{3\}$.

Test Case $3$: The final groups are $\{2, 3, 4, 6, 8\}$, $\{5\}$, and $\{7\}$.

Difficulty: MEDIUM_HARD
Tags: Number theory

Mathematics

Range queries
Skill types: Range queries

Starter code:

Solutions:
from bisect import bisect_right

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 * p, n + 1, p):
				prime[i] = False
		p += 1
		prime[2] = False
	lst = []
	for p in range(2, n + 1):
		if prime[p]:
			lst.append(p)
	return lst
m = 10 ** 7
val = Sieve(m)
for _ in range(int(input())):
	n = int(input())
	if n == 2:
		print('1')
	else:
		ans = bisect_right(val, n) - bisect_right(val, n // 2)
		print(ans + 1)


try:
	MAX = 10000000
	prefix = [0] * (MAX + 1)

	def buildPrefix():
		prime = [1] * (MAX + 1)
		p = 2
		while p * p <= MAX:
			if prime[p] == 1:
				i = p * 2
				while i <= MAX:
					prime[i] = 0
					i += p
			p += 1
		for p in range(2, MAX + 1):
			prefix[p] = prefix[p - 1]
			if prime[p] == 1:
				prefix[p] += 1

	def query(L, R):
		return prefix[R] - prefix[L - 1]
	buildPrefix()
	for t in range(int(input())):
		N = int(input())
		if N == 2:
			print(1)
			continue
		primes = query(N // 2 + 1, N)
		if primes == N - 1:
			print(primes)
		else:
			print(1 + primes)
except:
	pass


from bisect import *
import sys
input = sys.stdin.readline

def inp():
	return int(input())

def st():
	return input().rstrip('\n')

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

def ma():
	return map(int, input().split())
t = inp()
primes = []
vis = [0] * (10 ** 7 + 1)
for i in range(2, 10 ** 7 + 1):
	if vis[i]:
		continue
	for j in range(i, 10 ** 7 + 1, i):
		vis[j] = 1
	primes.append(i)
while t:
	t -= 1
	n = inp()
	if n == 2:
		print(1)
		continue
	elif n == 3:
		print(2)
		continue
	print(bisect_right(primes, n) - bisect_right(primes, n // 2) + 1)


from math import *
from sys import *
input = stdin.readline
n = 10 ** 7
p = [1] * (n + 1)
(p[0], p[1]) = (0, 0)
for i in range(2, int(sqrt(n + 1)) + 1):
	if p[i] == 1:
		for j in range(i * i, n + 1, i):
			p[j] = 0
for i in range(2, n + 1):
	p[i] = p[i] + p[i - 1]
for u in range(int(input())):
	n = int(input())
	if n == 2:
		print(1)
	elif n == 3:
		print(2)
	else:
		print(p[n] - p[n // 2] + 1)


def buildPrime():
	prime = [1] * (MAXIMUM + 1)
	p = 2
	while p * p <= MAXIMUM:
		if prime[p] == 1:
			i = p * 2
			while i <= MAXIMUM:
				prime[i] = 0
				i += p
		p += 1
	for p in range(2, MAXIMUM + 1):
		prefix[p] = prefix[p - 1]
		if prime[p] == 1:
			prefix[p] += 1

def answer(Left, Rright):
	return prefix[Rright] - prefix[Left - 1]
MAXIMUM = 10000000
prefix = [0] * (MAXIMUM + 1)
buildPrime()
t = int(input())
for case in range(t):
	n = int(input())
	if n < 4:
		print(answer(n // 2 + 1, n))
	else:
		print(1 + answer(n // 2 + 1, n))


limit = 10000000
arr = [True] * (limit + 1)
arr[0] = arr[1] = False
for i in range(int(limit ** 0.5)):
	if arr[i]:
		for j in range(i * 2, len(arr), i):
			arr[j] = False
primes = []
j = 0
for i in range(len(arr)):
	if arr[i]:
		j += 1
	primes.append(j)
for i in range(int(input())):
	n = int(input())
	if n < 4:
		print(primes[n] - primes[n // 2 - 1])
		continue
	print(primes[n] - primes[n // 2] + 1)


from itertools import accumulate
max = 10000000
sieve = [1 for i in range(max + 1)]
(sieve[0], sieve[1]) = (0, 0)
p = 2
while p * p <= max:
	if sieve[p]:
		for i in range(p * p, max + 1, p):
			sieve[i] = False
	p += 1
prime = list(accumulate(sieve))
t = int(input())
for _ in range(t):
	n = int(input())
	if n == 2:
		print(1)
	elif n == 3:
		print(2)
	else:
		print(1 + prime[n] - prime[n // 2])


from itertools import accumulate
n = 10000000
prime = [1 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
prime[0] = 0
prime[1] = 0
prime_number = list(accumulate(prime))
for testcase in range(int(input())):
	n = int(input())
	if n == 2:
		print(1)
	elif n == 3:
		print(2)
	else:
		print(1 + prime_number[n] - prime_number[n // 2])


from bisect import bisect_right

def prime(p):
	count = 0
	pre = [True for k in range(p + 1)]
	i = 2
	while i * i <= p:
		if pre[i] == True:
			for j in range(i + i, p + 1, i):
				pre[j] = False
		i += 1
	les = []
	for i in range(2, p + 1):
		if pre[i]:
			les.append(i)
	return les
s = pow(10, 7)
n = prime(s)
for i in range(int(input())):
	c = int(input())
	if c == 2:
		print(1)
	elif c == 3:
		print(2)
	else:
		ans = bisect_right(n, c) - bisect_right(n, c // 2)
		print(ans + 1)


prime = [True] * int(10000000.0 + 2)
prime[0] = prime[1] = False
prefix_prime = [0]

def sieve(N=int(10000000.0 + 1)):
	N = N + 1
	i = 2
	while i * i < N:
		if prime[i]:
			for j in range(i ** 2, N, i):
				prime[j] = False
		i += 1
sieve()

def precount_prime():
	count = 0
	for i in range(1, int(10000000.0 + 1)):
		if prime[i]:
			count += 1
		prefix_prime.append(count)
precount_prime()
for _ in range(int(input())):
	N = int(input())
	if N == 2:
		print(1)
	elif N == 3:
		print(2)
	else:
		f = 1 + prefix_prime[N] - prefix_prime[N // 2]
		print(f)


import bisect
primes = [True for i in range(10 ** 7 + 1)]
p = 2
while p * p <= 10 ** 7:
	if primes[p] == True:
		for i in range(p * p, 10 ** 7 + 1, p):
			primes[i] = False
	p = p + 1
pre = []
for i in range(2, 10 ** 7 + 1):
	if primes[i] == True:
		pre.append(i)
t = int(input())
for _ in range(t):
	n = int(input())
	if n == 2:
		print(1)
		continue
	if n == 3:
		print(2)
		continue
	count = bisect.bisect_right(pre, n) - bisect.bisect_right(pre, n // 2) + 1
	print(count)


t = int(input())
big = 10 ** 7 + 1
l = [1 for i in range(big + 1)]
l[0] = l[1] = 0
for i in range(2, int(big ** (1 / 2) + 1)):
	if l[i]:
		for j in range(i * i, big, i):
			l[j] = 0
c = 0
a = [0 for i in range(big + 1)]
for i in range(big + 1):
	if l[i] == 1:
		c += 1
	a[i] = c
for co in range(t):
	q = int(int(input()))
	v = q // 2
	if q == 2:
		print(1)
	elif q == 3:
		print(2)
	else:
		print(a[q] - a[v] + 1)


from itertools import accumulate
primes = [1 for _ in range(pow(10, 7) + 1)]
(primes[0], primes[1]) = (0, 0)
for num in range(2, 4 * pow(10, 3)):
	if primes[num] == 1:
		for x in range(2 * num, pow(10, 7) + 1, num):
			primes[x] = 0
primes[2] = 0
prime_cnt = list(accumulate(primes))
for _ in range(int(input())):
	n = int(input())
	print(prime_cnt[n] - prime_cnt[n // 2] + 1)


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
	li = [0, 0]
	x = 0
	for i in range(2, n):
		if prime[i]:
			x += 1
		li.append(x)
	return li
li = SieveOfEratosthenes(10 ** 7 + 1)
t = int(input())
while t > 0:
	t = t - 1
	ans = 1
	n = int(input())
	if n == 2:
		print(1)
	elif n == 3:
		print(2)
	else:
		print(li[n] - li[n // 2] + 1)


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

def pre():
	p1 = SieveOfEratosthenes(10 ** 7 + 1)
	prime = [None] * (10 ** 7 + 1)
	c = 0
	for i in range(10 ** 7 + 1):
		if p1[i]:
			c += 1
		prime[i] = c
	return prime
t = int(input())
prime = pre()
for i in range(1, t + 1):
	n = int(input())
	if n == 2:
		print(1)
		continue
	elif n == 3:
		print(2)
		continue
	groups = 1 + prime[n] - prime[n // 2]
	print(groups)


def sieve(arr, primes, m):
	for i in range(2, m + 1):
		arr[i] = arr[i - 1]
		if primes[i]:
			arr[i] += 1
			for j in range(2 * i, m + 1, i):
				primes[j] = 0
t = int(input())
n = []
m = 0
for i in range(t):
	n.append(int(input()))
	m = max(n[-1], m)
arr = [0] * (m + 1)
primes = [1] * (m + 1)
(primes[0], primes[1]) = (0, 0)
sieve(arr, primes, m)
for i in range(t):
	print(arr[n[i]] - max(1, arr[n[i] // 2]) + 1)


import math
size = 10 ** 7 + 1
prime = [1] * size
prime[0] = 0
prime[1] = 0
for i in range(2, math.ceil(math.sqrt(size)) + 1):
	if prime[i] == 1:
		for j in range(i * i, size, i):
			prime[j] = 0
for i in range(2, size):
	prime[i] = prime[i] + prime[i - 1]
for _ in range(int(input())):
	n = int(input())
	if n == 2:
		print(1)
	elif n == 3:
		print(2)
	else:
		print(prime[n] - prime[n // 2] + 1)


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
	prefixsumprime = [0 for i in range(n + 1)]
	for i in range(2, 10 ** 7 + 1):
		if prime[i]:
			prefixsumprime[i] = prefixsumprime[i - 1] + 1
		else:
			prefixsumprime[i] = prefixsumprime[i - 1]
	return prefixsumprime
prefixsumprime = SieveOfEratosthenes(10 ** 7)
for _ in range(int(input())):
	n = int(input())
	if n <= 3:
		print(n - 1)
	else:
		print(prefixsumprime[n] - prefixsumprime[n // 2] + 1)


query = []
for _ in range(int(input())):
	query.append(int(input()))
n = max(query)
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
dp = [0 for j in range(n + 1)]
(dp[1], dp[2]) = (1, 1)
for j in range(3, n + 1):
	if prime[j]:
		dp[j] = dp[j - 1] + 1
	else:
		dp[j] = dp[j - 1]
for j in query:
	print(dp[j] - dp[j // 2] + 1)


from math import sqrt, floor

def sieve(h):
	bl = [True] * (h + 1)
	a = [0] * (h + 1)
	for i in range(2, int(floor(sqrt(h))) + 1):
		if bl[i] == False:
			continue
		for j in range(i * i, h + 1, i):
			bl[j] = False
	c = 0
	for i in range(2, h + 1):
		if bl[i] == True:
			c += 1
		a[i] = c
	return a
prime = sieve(10000000)
t = int(input())
while t:
	m = int(input())
	if m == 2:
		print(1)
		t -= 1
		continue
	elif m == 3:
		print(2)
		t -= 1
		continue
	ans = prime[m] - prime[m // 2] + 1
	print(ans)
	t -= 1


N = int(10000000.0 + 2)

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
prime = sieve(N)

def pre_count(prime):
	prefix_prime = []
	count = 0
	for i in range(N + 1):
		if prime[i]:
			count += 1
		prefix_prime.append(count)
	return prefix_prime
prefix_prime = pre_count(prime)
t = int(input())
for _ in range(t):
	n = int(input())
	if n == 2:
		print(1)
	elif n == 3:
		print(2)
	else:
		lim = int(n / 2)
		extra = prefix_prime[n] - prefix_prime[lim]
		print(extra + 1)


import bisect
import sys

def get_inpt():
	return sys.stdin.readline().strip()

def get_int():
	return int(sys.stdin.readline().strip())

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_array():
	return list(map(int, sys.stdin.readline().strip().split()))

def p_str(x):
	sys.stdout.write(x + '\n')

def p_int(x):
	sys.stdout.write(str(x) + '\n')

def p_arr(arr):
	sys.stdout.write(' '.join(map(str, arr)) + '\n')

def SieveOfEratosthenes(n):
	arr = []
	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(2, n + 1):
		if prime[i] == True:
			arr.append(i)
	return arr

def solve(n, sieve):
	count = 1
	count += abs(bisect.bisect_right(sieve, n / 2) - bisect.bisect_right(sieve, n))
	if n == 2:
		return 1
	if n == 3:
		return 2
	return count
sieve = SieveOfEratosthenes(10000000)
for _ in range(get_int()):
	n = get_int()
	print(solve(n, sieve))


from sys import stdin
from bisect import bisect
N = 10 ** 7 + 1
isprime = [True for i in range(N)]
p = 2
while p * p < N:
	if isprime[p]:
		for i in range(p * p, N, p):
			isprime[i] = False
	p += 1
c = 0
ans = [0, 0]
for i in range(2, N):
	if isprime[i] == True:
		c += 1
	ans.append(c)
for _ in range(int(stdin.readline())):
	x = int(stdin.readline())
	a = ans[x // 2]
	b = ans[x]
	if a == 0:
		print(b)
	else:
		print(b - a + 1)


try:

	def sieve_of_eratosthenes():
		A = [0, 1]
		pr = 0
		j = int(10000000.0 + 1)
		prime = [True for i in range(j + 1)]
		B = []
		p = 2
		while p * p <= j:
			if prime[p]:
				for i in range(p * p, j + 1, p):
					prime[i] = False
			p += 1
		for p in range(2, j + 1):
			if prime[p]:
				pr += 1
			A.append(pr)
		return A
	arr = sieve_of_eratosthenes()
	for _ in range(int(input())):
		N = int(input())
		print(arr[N] - arr[int(N / 2)] + 1)
except:
	pass


try:

	def seivelist(n):
		a = [0] * (n + 1)
		sqrtn = int(n ** 0.5)
		curprime = 2
		primesprefixsum = [0] * (n + 1)
		nextprime = 2
		while curprime <= sqrtn:
			j = 2
			curprime = nextprime
			primemul = curprime * j
			while primemul < n + 1:
				a[primemul] = -1
				j += 1
				primemul = j * curprime
			for i in range(curprime + 1, sqrtn + 1):
				if a[i] == 0:
					nextprime = i
					break
			if nextprime == curprime:
				break
		for i in range(2, n + 1):
			primesprefixsum[i] = primesprefixsum[i - 1]
			if a[i] == 0:
				primesprefixsum[i] += 1
		return primesprefixsum
	maxn = -1
	a = []
	for _ in range(int(input())):
		n = int(input())
		a.append(n)
		maxn = max(n, maxn)
	pps = seivelist(maxn)
	for n in a:
		ans = pps[n] - pps[n // 2] + 1
		if n < 4:
			ans -= 1
		print(ans)
except EOFError:
	pass


from sys import stdin, stdout
input = stdin.readline

def im():
	return map(int, input().split())

def ii():
	return int(input())

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

def ins():
	return input()[:-1]
N = int(10000000.0) + 5
prime = [1] * N
prime[0] = prime[1] = 0
i = 2
while i * i < N:
	if prime[i] == 1:
		for j in range(i * i, N, i):
			prime[j] = 0
	i += 1
prime[3] = 2
for i in range(4, N):
	prime[i] += prime[i - 1]
for _ in range(ii()):
	n = ii()
	if n == 2:
		print(1)
	elif n == 3:
		print(2)
	else:
		print(prime[n] - prime[n // 2] + 1)


def sieve(n):
	l = [True for i in range(n + 1)]
	(l[0], l[1]) = (False, False)
	for i in range(2, int(n ** 0.5) + 1):
		if l[i] == True:
			for i in range(i * i, n + 1, i):
				l[i] = False
	return l
r = sieve(10 ** 7 + 2)
(c, l) = (0, [])
for i in range(0, 10 ** 7 + 1):
	if r[i] == True:
		c += 1
	l.append(c)
for _ in range(int(input())):
	n = int(input())
	if n == 2:
		print(1)
	elif n == 3:
		print(2)
	else:
		print(1 + l[n] - l[n // 2])


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
	prefix = [0 for jk in range(n)]
	for p in range(2, n):
		if prime[p]:
			c += 1
		prefix[p] = c
	return prefix
x = SieveOfEratosthenes(int(10000000.0 + 2))
for t in range(int(input())):
	N = int(input())
	if N == 2:
		print('1')
	elif N == 3:
		print('2')
	else:
		l = int(N / 2)
		tot = x[N] - x[l]
		print(tot + 1)


import numpy as np
t = int(input())
n = int(10000000.0 + 5)
prime = np.ones(n, dtype=int)
prime[0] = 0
prime[1] = 0
p = 2
while p * p <= n:
	if prime[p] == 1:
		indices = np.arange(2 * p, n, p)
		values = np.zeros(len(indices))
		np.put(prime, indices, values)
	p += 1
prime[2] = 0
prime = np.cumsum(prime)
for _ in range(t):
	c = int(input())
	print(prime[c] - prime[c // 2] + 1)


import sys
from os import path
import math
import time
from collections import defaultdict
from sys import setrecursionlimit
setrecursionlimit(10 ** 8)
MOD = 10 ** 9 + 7
INT_MAX = 10 ** 9
if path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

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 * 2, n + 1, p):
				prime[i] = False
		p += 1
	prime[0] = False
	prime[1] = False
	no_prime = []
	count = 0
	for i in range(len(prime)):
		if prime[i]:
			count += 1
		no_prime.append(count)
	return no_prime

def test_case():
	t = int(input())
	p = SieveOfEratosthenes(10000000 + 2)
	for _ in range(t):
		n = int(input())
		if n > 3:
			count = p[n] - p[int(n / 2)] + 1
		else:
			count = n - 1
		print(count)
test_case()


def SieveOfEratosthenes(n):
	halp = []
	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(2, n + 1):
		if prime[p]:
			halp.append(p)
	return halp
sa = SieveOfEratosthenes(10 ** 7)
from bisect import bisect_left
for _ in range(int(input())):
	n = int(input())
	if n == 2:
		print(1)
		continue
	elif n == 3:
		print(2)
		continue
	else:
		print(bisect_left(sa, n + 1) - bisect_left(sa, n // 2 + 1) + 1)


def seive(n):
	prefix_ar = [0 for i in range(n + 1)]
	ls = [True for i in range(n + 1)]
	ls[0] = False
	ls[1] = False
	for i in range(2, n + 1):
		val = ls[i]
		if i * i <= n + 1:
			if val == True:
				for j in range(i * i, n + 1, i):
					if j % i == 0:
						ls[j] = False
		else:
			break
	for i in range(1, n + 1):
		val = ls[i]
		if val == True:
			prefix_ar[i] = prefix_ar[i - 1] + 1
		else:
			prefix_ar[i] = prefix_ar[i - 1]
	return prefix_ar

def fun(lx, mx):
	n = mx
	prefix_ar = seive(n)
	for i in lx:
		if i == 2:
			print(1)
			continue
		if i == 3:
			print(2)
			continue
		print(1 + prefix_ar[i] - prefix_ar[i // 2])
T = int(input())
mx = 0
ls = []
for _ in range(T):
	n = int(input())
	ls.append(n)
	mx = max(mx, n)
fun(ls, mx)


def SieveOfEratosthenes(n, d):
	c = 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
	return prime
b = []
d = {}
b = SieveOfEratosthenes(10000001, d)
p = 0
for i in range(2, 10000001):
	if b[i] == True:
		p += 1
		d[i] = p
t = int(input())
for test in range(t):
	n = int(input())
	c = 0
	if n == 2:
		print(1)
	elif n == 3:
		print(2)
	else:
		c = 0
		x = 0
		z = n // 2
		for i in range(n, z, -1):
			if b[i] == True:
				x = d[i]
				break
		for i in range(z, 1, -1):
			if b[i] == True:
				c = d[i]
				break
		print(x - c + 1)


t = int(input())

def SieveOfEratosthenes(n):
	prime = [1 for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == 1:
			for i in range(p * p, n + 1, p):
				prime[i] = 0
		p += 1
	return prime
c = SieveOfEratosthenes(10 ** 7 + 1)
for i in range(3, len(c) // 2):
	if c[i] == 1:
		c[2 * i] = -1
		c[i] = 1
for i in range(3, len(c)):
	c[i] += c[i - 1]
for i in range(t):
	n = int(input())
	h = 0
	print(c[n])


N = int(10000000.0 + 1)
prime = [True for i in range(N + 1)]
prefix = [0] * (N + 2)

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

def func():
	prefix[2] = 1
	prefix[3] = 2
	prefix[4] = 2
	count = 2
	for p in range(5, N + 1):
		if prime[p]:
			count += 1
		elif p % 2 == 0 and prime[p // 2]:
			count -= 1
		prefix[p] = count
siev()
func()
for _ in range(int(input())):
	n = int(input())
	print(prefix[n])


prime = [True for i in range(10000001)]
p = 2
while p * p < 10000001:
	if prime[p] == True:
		for i in range(p * p, 10000001, p):
			prime[i] = False
	p += 1
tpr = 0
tprime = []
for i in range(2, 10000001):
	if prime[i]:
		tpr += 1
	tprime.append(tpr)
for _ in range(int(input())):
	n = int(input())
	start = tprime[n // 2 - 2]
	end = tprime[n - 2]
	if n == 2:
		print(1)
	elif n == 3:
		print(2)
	else:
		print(end - start + 1)


def SieveOfEratosthenes():
	a = [0] * 10000001
	n = 10000000
	cnt = 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(2, n + 1):
		if prime[p]:
			cnt += 1
		a[p] = cnt
	return a
T = int(input())
num = SieveOfEratosthenes()
while T > 0:
	N = int(input())
	if N == 2:
		print(1)
		T -= 1
		continue
	if N == 3:
		print(2)
		T -= 1
		continue
	even = N // 2
	print(num[N] - (num[N // 2] - 1))
	T -= 1


from bisect import bisect_right

def primes_upto(limit):
	is_prime = [True] * (limit + 1)
	for n in range(3, int(limit ** 0.5 + 1.5), 2):
		if is_prime[n]:
			for i in range(n * n, limit + 1, 2 * n):
				is_prime[i] = False
	for i in range(3, limit + 1, 2):
		if is_prime[i]:
			yield i
	return
p = list(primes_upto(10 ** 7))

def sol(n):
	if n == 2:
		return 1
	return bisect_right(p, n) - bisect_right(p, n // 2) + 1
for _ in range(int(input())):
	print(sol(int(input())))


N = 10000002
prime = [True] * (N + 1)
prefixsum = [0] * (N + 1)

def sieve():
	prime[0] = prime[1] = False
	i = 2
	while i * i < N:
		if prime[i]:
			for j in range(i * i, N + 1, i):
				prime[j] = False
		i += 1

def pref():
	cnt = 0
	for i in range(1, N + 1):
		if prime[i]:
			cnt += 1
		prefixsum[i] = cnt
sieve()
pref()
t = int(input())
while t:
	n = int(input())
	if n == 2:
		print(1)
	elif n == 3:
		print(2)
	else:
		print(1 + prefixsum[n] - prefixsum[n // 2])
	t -= 1


import bisect
T = int(input())
n = 10 ** 7
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
l = []
for p in range(2, n + 1):
	if prime[p]:
		l.append(p)
for i in range(T):
	n = int(input())
	r1 = bisect.bisect_right(l, n / 2)
	r2 = bisect.bisect_right(l, n)
	if n < 4:
		print(r2 - r1)
	else:
		print(r2 - r1 + 1)


import math
n = pow(10, 7) + 2
ar = [1] * n
ar[0] = ar[1] = 0
ar2 = [0] * n
for i in range(2, n):
	if i * i >= n:
		break
	if ar[i]:
		for j in range(i * i, n, i):
			ar[j] = 0
c = 0
for i in range(1, n):
	if ar[i]:
		c += 1
	ar2[i] = c
for i in range(int(input())):
	n1 = int(input())
	if n1 == 2:
		print(1)
	elif n1 == 3:
		print(2)
	else:
		a = n1 // 2
		b = ar2[n1] - ar2[a] + 1
		print(b)


try:

	def Ss(n):
		op = []
		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
		for p in range(n + 1):
			if prime[p]:
				op.append(p)
		return op
	kl = Ss(10 ** 7)
	import bisect
	t = int(input())
	for i in range(0, t):
		n = int(input())
		if n == 2:
			print(1)
		elif n == 3:
			print(2)
		else:
			tn = bisect.bisect_right(kl, n) - bisect.bisect_right(kl, n // 2)
			print(tn + 1)
except:
	pass


t = int(input())
l = [0] * (10 ** 7 + 1)

def seive(maxi):
	prime = [True for i in range(maxi + 1)]
	p = 2
	c = 0
	while p * p <= maxi:
		if prime[p] == True:
			for i in range(p * p, maxi + 1, p):
				prime[i] = False
		p += 1
	for p in range(2, maxi + 1):
		if prime[p]:
			c += 1
		l[p] = c
seive(10 ** 7)
for _ in range(t):
	n = int(input())
	if n <= 3:
		print(n - 1)
	else:
		ans = l[n] - l[n // 2] + 1
		print(ans)


lim = 10000000
util = [0] * 10000001

def helper():
	isp = [True] * 10000001
	i = 2
	while i * i <= lim:
		if isp[i] == True:
			j = i * 2
			while j <= lim:
				isp[j] = False
				j += i
		i += 1
	util[0] = 0
	util[1] = 0
	i = 2
	while i <= lim:
		util[i] = util[i - 1]
		if isp[i]:
			util[i] += 1
		i += 1
helper()
t = int(input())
while t > 0:
	n = int(input())
	if n == 2:
		print(1)
	elif n == 3 or n == 4:
		print(2)
	else:
		mid = n // 2
		res = util[n] - util[mid]
		print(res + 1)
	t -= 1


from math import ceil, sqrt

def steve(n):
	global isPrime
	isPrime = [1] * (n + 1)
	isPrime[0] = isPrime[1] = 0
	for i in range(2, int(sqrt(n)) + 1):
		if isPrime[i]:
			isPrime[i * i:n + 1:i] = [0] * len(isPrime[i * i:n + 1:i])
steve(10000000)
for i in range(1, 10000001):
	isPrime[i] += isPrime[i - 1]
for _ in range(int(input())):
	n = int(input())
	if n == 2 or n == 3:
		print(n - 1)
	else:
		print(isPrime[n] - isPrime[n // 2] + 1)


n = 10 ** 7
seive = [False] * (n + 1)
(seive[0], seive[1]) = (True, True)
p = 2
while p * p <= n:
	if seive[p] == False:
		for i in range(p * p, len(seive), p):
			seive[i] = True
	p += 1

def is_prime(n):
	return not seive[n]
table = [0] * (n + 1)
table[2] = 1
for i in range(2, len(table)):
	if is_prime(i):
		table[i] = table[i - 1] + 1
	else:
		table[i] = table[i - 1]

def solve(n):
	l = [1, 2, 2, 3]
	if n < 6:
		return l[n - 2]
	else:
		return table[n] - table[n // 2] + 1
t = int(input())
for tc in range(t):
	n = int(input())
	print(solve(n))


def primeNumbers():
	prime[0] = prime[1] = False
	i = 2
	while i * i < n:
		if prime[i]:
			j = i * i
			while j <= n:
				prime[j] = False
				j += i
		i += 1

def pre():
	count = 0
	for i in range(1, n + 1):
		if prime[i]:
			count += 1
		prefix[i] = count

def totalComponents(m):
	if 2 <= m <= 3:
		return m - 1
	return prefix[m] - prefix[m // 2] + 1
t = int(input())
a = [0] * t
for i in range(t):
	a[i] = int(input())
n = max(a)
prime = [True] * (n + 1)
prefix = [0] * (n + 1)
primeNumbers()
pre()
for i in range(t):
	print(totalComponents(a[i]))


def prime(n):
	i = 2
	global l
	while i * i < n:
		if arr[i] == True:
			for j in range(i * i, n, i):
				arr[j] = False
		i += 1
	count = 0
	for i in range(2, n):
		if arr[i]:
			count += 1
		prime_count[i] = count
n = 10 ** 7 + 1
arr = [True] * n
prime_count = [0] * n
prime(n)
t = int(input())
while t:
	N = int(input())
	if N == 2:
		print(1)
	elif N == 3:
		print(2)
	else:
		print(prime_count[N] - prime_count[N // 2] + 1)
	t -= 1


from sys import stdin, stdout
import math, bisect, heapq
from collections import Counter, deque, defaultdict
L = lambda : list(map(int, stdin.readline().strip().split()))
I = lambda : int(stdin.readline().strip())
S = lambda : stdin.readline().strip()
C = lambda : stdin.readline().strip().split()

def pr(a):
	return '.'.join(list(map(str, a)))
a = []

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 * p, n + 1, p):
				prime[i] = False
		p += 1
	prime[0] = False
	prime[1] = False
	x = 0
	for i in range(n + 1):
		if prime[i]:
			x += 1
		a.append(x)

def solve():
	n = I()
	if n == 2:
		print(1)
	elif n == 3:
		print(2)
	else:
		print(a[n] - a[n // 2] + 1)
sieve(10 ** 7)
for _ in range(I()):
	solve()


def SieveOfEratosthenes(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
	return prime

def func():
	MAX = 10 ** 7 + 1
	prime = SieveOfEratosthenes(MAX)
	prefix_arr = [0, 0]
	for i in range(2, MAX):
		if prime[i]:
			prefix_arr.append(prefix_arr[-1] + 1)
		else:
			prefix_arr.append(prefix_arr[-1])
	return prefix_arr
prefix_arr = func()
for _ in range(int(input())):
	N = int(input())
	if N <= 3:
		print(prefix_arr[N])
	else:
		print(prefix_arr[N] - prefix_arr[N // 2] + 1)


def seive(n):
	prefix_ar = [0 for i in range(n + 1)]
	ls = [True for i in range(n + 1)]
	ls[0] = False
	ls[1] = False
	for i in range(2, n + 1):
		val = ls[i]
		if i * i <= n + 1:
			if val == True:
				for j in range(i * i, n + 1, i):
					if j % i == 0:
						ls[j] = False
		else:
			break
	for i in range(1, n + 1):
		val = ls[i]
		if val == True:
			prefix_ar[i] = prefix_ar[i - 1] + 1
		else:
			prefix_ar[i] = prefix_ar[i - 1]
	return prefix_ar
n = 10 ** 7 + 1
prefix_ar = seive(n)
T = int(input())
mx = 0
ls = []
for _ in range(T):
	i = int(input())
	if i == 2:
		print(1)
		continue
	if i == 3:
		print(2)
		continue
	print(1 + prefix_ar[i] - prefix_ar[i // 2])


import math
n = 10 ** 7 + 1
prime = [1] * n
prime[0] = 0
prime[1] = 0
for i in range(2, math.ceil(math.sqrt(n)) + 1):
	if prime[i] == 1:
		for j in range(i * i, n, i):
			prime[j] = 0
for i in range(2, n):
	prime[i] += prime[i - 1]
t = int(input())
for i in range(t):
	ni = int(input())
	if ni > 3:
		c = prime[ni] - prime[ni // 2] + 1
		print(c)
	elif ni == 2:
		print(1)
	else:
		print(2)


primeUpto = [0] * 10000003
prime = [1] * 10000003
prime[0] = prime[1] = 0

def countPrime():
	n = 10000001
	p = 2
	while p * p <= n:
		if prime[p] == 1:
			for i in range(p * p, n + 1, p):
				prime[i] = 0
		p += 1
	for i in range(1, 10000002):
		primeUpto[i] = primeUpto[i - 1] + prime[i]
countPrime()
for _ in range(int(input())):
	n = int(input())
	if n == 3:
		print(2)
	elif n == 2:
		print(1)
	else:
		print(primeUpto[n] - primeUpto[n // 2] + 1)


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(2 * p, n + 1, p):
				prime[i] = False
		p += 1
	prime[0] = False
	prime[1] = False
	return prime
primes = SieveOfEratosthenes(10 ** 7 + 5)
count_1 = 0
pricount = [0]
for i in range(1, 10 ** 7 + 6):
	if primes[i]:
		count_1 += 1
	pricount.append(count_1)
for i in range(int(input())):
	n = int(input())
	j = 0
	x = 1
	y = 1
	count = 0
	if n == 2:
		print(1)
		continue
	elif n == 3:
		print(2)
		continue
	print(pricount[n] - pricount[n // 2] + 1)


import sys
from math import ceil
input = sys.stdin.readline
p = [False] + [True] * 10 ** 7
p[1] = False
p_count = [0] * (10 ** 7 + 1)
for i in range(2, 10 ** 7 + 1):
	p_count[i] = p_count[i - 1]
	if p[i]:
		p_count[i] += 1
		for j in range(i * i, 10 ** 7 + 1, i):
			p[j] = False
for _ in range(int(input())):
	n = int(input())
	if n == 2:
		print(1)
		continue
	if n == 3:
		print(2)
		continue
	print(p_count[n] - p_count[n // 2] + 1)


import math
n = 10 ** 7 + 1
prime = [True] * n
prime_count = [0] * n
p = 2
while p * p < n:
	if prime[p]:
		for i in range(p * p, n, p):
			prime[i] = False
	p += 1
count = 0
for i in range(2, n):
	if prime[i]:
		count += 1
	prime_count[i] = count
t = int(input())
while t:
	n = int(input())
	if n == 2:
		print('1')
	elif n == 3:
		print('2')
	else:
		print(prime_count[n] - prime_count[n // 2] + 1)
	t -= 1


import math
N = 10 ** 7 + 1
prime = []
primecount = [0, 0]
sieve = [False for i in range(N)]
k = 2
while k <= int(math.sqrt(N)):
	if sieve[k] == False:
		for i in range(k ** 2, N, k):
			sieve[i] = True
	k += 1
for i in range(2, N):
	if sieve[i]:
		primecount.append(primecount[-1])
	else:
		prime.append(i)
		primecount.append(primecount[-1] + 1)
t = int(input())
for testcase in range(t):
	n = int(input())
	if n == 2:
		print(1)
	elif n == 3:
		print(2)
	else:
		limit = n // 2
		i = 0
		print(primecount[n] - primecount[limit] + 1)