In number world, two different numbers are friends if they have a lot in common, but also each one has unique perks.

More precisely, two different numbers $a$ and $b$ are friends if $gcd(a,b)$, $\frac{a}{gcd(a,b)}$, $\frac{b}{gcd(a,b)}$ can form sides of a triangle.

Three numbers $a$, $b$ and $c$ can form sides of a triangle if $a + b > c$, $b + c > a$ and $c + a > b$.

In a group of numbers, a number is lonely if it doesn't have any friends in that group.

Given a group of numbers containing all numbers from $1, 2, 3, ..., n$, how many numbers in that group are lonely?


-----Input-----

The first line contains a single integer $t$ $(1 \leq t \leq 10^6)$ - number of test cases.

On next line there are $t$ numbers, $n_i$ $(1 \leq n_i \leq 10^6)$ - meaning that in case $i$ you should solve for numbers $1, 2, 3, ..., n_i$.


-----Output-----

For each test case, print the answer on separate lines: number of lonely numbers in group $1, 2, 3, ..., n_i$.


-----Example-----
Input
3
1 5 10

Output
1
3
3



-----Note-----

For first test case, $1$ is the only number and therefore lonely.

For second test case where $n=5$, numbers $1$, $3$ and $5$ are lonely.

For third test case where $n=10$, numbers $1$, $5$ and $7$ are lonely.

Difficulty: competition

Starter code:

Solutions:
import os
import sys
from io import BytesIO, IOBase


def main():
    pass


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

primes = []
prime = [True] * (10 ** 6  +5)
prime[0] = False

for i in range(2, 10 ** 6):
    if prime[i]:
        for j in range(2 * i, 10 ** 6 + 5, i):
            prime[j] = False

pref = [0]
for i in range(1, 10 ** 6 + 5):
    pref.append(pref[-1])
    if prime[i]:
        pref[-1] += 1
    s = round(i ** .5)
    if  s * s == i and prime[s] and i != 1:
        pref[-1] -= 1

n = int(input())
l = list(map(int, input().split()))
out = []
for v in l:
    out.append(pref[v])
print('\n'.join(map(str,out)))


import os
import sys
from io import BytesIO, IOBase
 
# region fastio
BUFSIZE = 8192
class FastIO(IOBase):
    newlines = 0
 
    def __init__(self, file):
        import os
        self.os = os
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
 
    def read(self):
        while True:
            b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
 
    def readline(self):
        while self.newlines == 0:
            b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
 
    def flush(self):
        if self.writable:
            self.os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
 
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
 
 
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

"""
New numbers are only lonely if prime.
When does a prime stop being lonely

"""

def get_p(n):
    """ Returns  a list of primes < n """
    z = int(n**0.5)+1
    for s in range(4,len(sieve),2):
        sieve[s] = False
    for i in range(3,z,2):
        if sieve[i]:
            sieve[i*i::2*i]=[False]*((n-i*i-1)//(2*i)+1)
            if i <= 1000:
                sq_primes.add(i*i)
    return

lim = 10**6
sieve = [True]*(lim+1)
sq_primes = set()
sq_primes.add(4)
get_p(lim+1)
ans = [0,1]
for i in range(2,10**6+1):
    tmp = ans[-1]
    if sieve[i]:
        tmp += 1
    elif i in sq_primes:
        tmp -= 1
    ans.append(tmp) 


def solve():
    T = int(input().strip())
    A = [int(s) for s in input().split()]
    print(*[ans[A[j]] for j in range(T)])
    return 
solve()
#print(time.time()-start_time)


import os
import sys
from io import BytesIO, IOBase
# region fastio
BUFSIZE = 8192
class FastIO(IOBase):
    newlines = 0
 
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
 
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
 
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
 
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
 
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
 
 
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
 
# ------------------------------
 
def RL(): return list(map(int, sys.stdin.readline().rstrip().split()))
def RLL(): return list(map(int, sys.stdin.readline().rstrip().split()))
def N(): return int(input())
def print_list(l):
    print(' '.join(map(str,l)))
# import sys
# sys.setrecursionlimit(5010)
# from heapq import *
# from collections import deque as dq
from math import ceil,floor,sqrt,pow
# import bisect as bs
# from collections import Counter
# from collections import defaultdict as dc 

def judgePrime(n):
    if n < 2:
        return []     
    else:
        output = [1] * n
        output[0],output[1] = 0,0
        for i in range(2,int(n**0.5)+1): 
            if output[i] == 1:
                output[i*i:n:i] = [0] * len(output[i*i:n:i])
    return output

prime = judgePrime(1000005)
s = [0]
for i in range(1,1000005):
    s.append(s[-1]+prime[i])

t = N()
a = RL()
for n in a:
    print(s[n]-s[int(sqrt(n))]+1)


import sys
input=sys.stdin.buffer.readline #FOR READING PURE INTEGER INPUTS (space separation ok)


MAXPRIME=10**6
isPrime=[0 for _ in range(MAXPRIME+1)]
isPrime[0]=-1;isPrime[1]=-1 #0 and 1 are not prime numbers
for i in range(2,MAXPRIME//2+1):
    if isPrime[i]==0: #i is prime
        for multiple in range(i*i,MAXPRIME+1,i):
            if isPrime[multiple]==0:
                isPrime[multiple]=i         
primeNumberSet=set()
for i in range(len(isPrime)):
    if isPrime[i]==0:
        primeNumberSet.add(i)
primes=sorted(list(primeNumberSet))

lookupTable=[None for _ in range(MAXPRIME+1)]

pIdx=-1
pSqRtIdx=-1
for i in range(1,MAXPRIME+1):
    while pIdx+1<len(primes) and primes[pIdx+1]<=i:
        pIdx+=1
    while pSqRtIdx+1<len(primes) and (primes[pSqRtIdx+1])**2<=i:
        pSqRtIdx+=1
    total=(pIdx+1)-(pSqRtIdx+1)+1 #1 is always lonely
    lookupTable[i]=total

#print(lookupTable[:30])

#a number is lonely if its gcd with all other numbers is 1. i.e. it is prime and its square > n. also, 1 is always lonely
t=int(input())
n=[int(x) for x in input().split()]
for nn in n:
    print(lookupTable[nn])




#def gcd(x, y):
#    while y != 0:
#        (x, y) = (y, x % y)
#    return x
#lonely=[]
#for i in range(1,n+1):
#    ok=False
#    for j in range(1,n+1):
#        g=gcd(i,j)
#        a=g
#        b=i//g
#        c=j//g
#        if a+b>c and b+c>a and a+c>b:
#            ok=True
#            if i in primeNumberSet:
#                print(i,j)
#            break
#    if ok==False:
#        lonely.append(i)
#print(lonely)


import sys
input=sys.stdin.buffer.readline #FOR READING PURE INTEGER INPUTS (space separation ok)

MAXPRIME=10**6
isPrime=[0 for _ in range(MAXPRIME+1)]
isPrime[0]=-1;isPrime[1]=-1 #0 and 1 are not prime numbers
for i in range(2,MAXPRIME//2+1):
    if isPrime[i]==0: #i is prime
        for multiple in range(i*i,MAXPRIME+1,i):
            if isPrime[multiple]==0:
                isPrime[multiple]=i         
primeNumberSet=set()
for i in range(len(isPrime)):
    if isPrime[i]==0:
        primeNumberSet.add(i)
primes=sorted(list(primeNumberSet))

lookupTable=[None for _ in range(MAXPRIME+1)]

pIdx=-1
pSqRtIdx=-1
for i in range(1,MAXPRIME+1):
    while pIdx+1<len(primes) and primes[pIdx+1]<=i:
        pIdx+=1
    while pSqRtIdx+1<len(primes) and (primes[pSqRtIdx+1])**2<=i:
        pSqRtIdx+=1
    total=(pIdx+1)-(pSqRtIdx+1)+1 #1 is always lonely
    lookupTable[i]=total

#print(lookupTable[:30])

#a number is lonely if its gcd with all other numbers is 1. i.e. it is prime and its square > n. also, 1 is always lonely
t=int(input())
n=[int(x) for x in input().split()]
ans=[str(lookupTable[nn]) for nn in n]
print('\n'.join(ans))

import sys
input=sys.stdin.buffer.readline #FOR READING PURE INTEGER INPUTS (space separation ok)

MAXPRIME=10**6
isPrime=[0 for _ in range(MAXPRIME+1)]
isPrime[0]=-1;isPrime[1]=-1 #0 and 1 are not prime numbers
for i in range(2,MAXPRIME//2+1):
    if isPrime[i]==0: #i is prime
        for multiple in range(i*i,MAXPRIME+1,i):
            if isPrime[multiple]==0:
                isPrime[multiple]=i         
primeNumberSet=set()
for i in range(len(isPrime)):
    if isPrime[i]==0:
        primeNumberSet.add(i)
primes=sorted(list(primeNumberSet))

lookupTable=[None for _ in range(MAXPRIME+1)]

pIdx=-1
pSqRtIdx=-1
for i in range(1,MAXPRIME+1):
    while pIdx+1<len(primes) and primes[pIdx+1]<=i:
        pIdx+=1
    while pSqRtIdx+1<len(primes) and (primes[pSqRtIdx+1])**2<=i:
        pSqRtIdx+=1
    total=(pIdx+1)-(pSqRtIdx+1)+1 #1 is always lonely
    lookupTable[i]=total

#print(lookupTable[:30])

#a number is lonely if its gcd with all other numbers is 1. i.e. it is prime and its square > n. also, 1 is always lonely
t=int(input())
n=[int(x) for x in input().split()]
print('\n'.join([str(lookupTable[nn]) for nn in n]))

import os
import sys
from io import BytesIO, IOBase
# region fastio
BUFSIZE = 8192
class FastIO(IOBase):
    newlines = 0
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

MAXPRIME=10**6
isPrime=[0 for _ in range(MAXPRIME+1)]
isPrime[0]=-1;isPrime[1]=-1 #0 and 1 are not prime numbers
for i in range(2,MAXPRIME//2+1):
    if isPrime[i]==0: #i is prime
        for multiple in range(i*i,MAXPRIME+1,i):
            if isPrime[multiple]==0:
                isPrime[multiple]=i         
primeNumberSet=set()
for i in range(len(isPrime)):
    if isPrime[i]==0:
        primeNumberSet.add(i)
primes=sorted(list(primeNumberSet))

lookupTable=[None for _ in range(MAXPRIME+1)]

pIdx=-1
pSqRtIdx=-1
for i in range(1,MAXPRIME+1):
    while pIdx+1<len(primes) and primes[pIdx+1]<=i:
        pIdx+=1
    while pSqRtIdx+1<len(primes) and (primes[pSqRtIdx+1])**2<=i:
        pSqRtIdx+=1
    total=(pIdx+1)-(pSqRtIdx+1)+1 #1 is always lonely
    lookupTable[i]=total

#print(lookupTable[:30])

#a number is lonely if its gcd with all other numbers is 1. i.e. it is prime and its square > n. also, 1 is always lonely
t=int(input())
n=[int(x) for x in input().split()]
print('\n'.join([str(lookupTable[nn]) for nn in n]))

# ------------------- fast io --------------------
import os
import sys
from io import BytesIO, IOBase
 
BUFSIZE = 8192
 
class FastIO(IOBase):
    newlines = 0
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
 
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
 
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
 
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
 
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
 
 
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
# ------------------- fast io --------------------
from bisect import bisect_left as bsl;import math
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
    pp=[]
    for p in range(n + 1): 
        if prime[p]: 
            pp.append(p)
    return pp
primes=sieve(10**6)
t=int(input());vals=list(map(int,input().split()))
for j in range(t):
    n=vals[j]
    ind1=min(bsl(primes,math.floor(math.sqrt(n))),len(primes)-1)
    ind2=min(bsl(primes,n),len(primes)-1)
    if primes[ind1]>math.floor(math.sqrt(n)):
        ind1-=1
    if primes[ind2]>n:
        ind2-=1
    print(ind2+1-ind1)

"""
    Author - Satwik Tiwari .
    27th Sept , 2020  - Sunday
"""

#===============================================================================================
#importing some useful libraries.



from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase


# from itertools import *
from heapq import *
# from math import gcd, factorial,floor,ceil

from copy import deepcopy
from collections import deque


# from collections import Counter as counter  # Counter(list)  return a dict with {key: count}
# from itertools import combinations as comb # if a = [1,2,3] then print(list(comb(a,2))) -----> [(1, 2), (1, 3), (2, 3)]
# from itertools import permutations as permutate


from bisect import bisect_left as bl
from bisect import bisect_right as br
from bisect import bisect

#==============================================================================================
#fast I/O region
BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

# inp = lambda: sys.stdin.readline().rstrip("\r\n")

#===============================================================================================
### START ITERATE RECURSION ###
from types import GeneratorType
def iterative(f, stack=[]):
  def wrapped_func(*args, **kwargs):
    if stack: return f(*args, **kwargs)
    to = f(*args, **kwargs)
    while True:
      if type(to) is GeneratorType:
        stack.append(to)
        to = next(to)
        continue
      stack.pop()
      if not stack: break
      to = stack[-1].send(to)
    return to
  return wrapped_func
#### END ITERATE RECURSION ####

#===============================================================================================
#some shortcuts

mod = 10**9+7
def inp(): return sys.stdin.readline().rstrip("\r\n") #for fast input
def out(var): sys.stdout.write(str(var))  #for fast output, always take string
def lis(): return list(map(int, inp().split()))
def stringlis(): return list(map(str, inp().split()))
def sep(): return list(map(int, inp().split()))
def strsep(): return list(map(str, inp().split()))
# def graph(vertex): return [[] for i in range(0,vertex+1)]
def zerolist(n): return [0]*n
def nextline(): out("\n")  #as stdout.write always print sring.
def testcase(t):
    for pp in range(t):
        solve(pp)
def printlist(a) :
    for p in range(0,len(a)):
        out(str(a[p]) + ' ')
def google(p):
    print('Case #'+str(p)+': ',end='')
def lcm(a,b): return (a*b)//gcd(a,b)
def power(x, y, p) :
    res = 1     # Initialize result
    x = x % p  # Update x if it is more , than or equal to p
    if (x == 0) :
        return 0
    while (y > 0) :
        if ((y & 1) == 1) : # If y is odd, multiply, x with result
            res = (res * x) % p

        y = y >> 1      # y = y/2
        x = (x * x) % p
    return res
def ncr(n,r): return factorial(n) // (factorial(r) * factorial(max(n - r, 1)))
def isPrime(n) :
    if (n <= 1) : return False
    if (n <= 3) : return True
    if (n % 2 == 0 or n % 3 == 0) : return False
    i = 5
    while(i * i <= n) :
        if (n % i == 0 or n % (i + 2) == 0) :
            return False
        i = i + 6
    return True

#===============================================================================================
# code here ;))
ans = [0]*(10**6+5)

def sieve(a): #O(n loglogn) nearly linear
    #all odd mark 1
    for i in range(3,((10**6)+5),2):
        a[i] = 1
    #marking multiples of i form i*i 0. they are nt prime
    for i in range(3,((10**6)+5),2):
        for j in range(i*i,((10**6)+5),i):
            a[j] = 0
    a[2] = 1 #special left case
    return (a)


a = [0]*((10**6)+6)
a = sieve(a)
primes = []
for i in range(10**6+1):
    if(a[i]):
        primes.append(i)

# primes = primes[1:]
# print(ans[:20])


for i in primes:
    ans[i] += 1
    ans[min(10**6+2,i*i)] -=1

# print(ans[:20])
for i in range(2,10**6+1):
    ans[i] +=ans[i-1]

# print(ans[:20])


def solve(case):
    n = int(inp())
    aa = lis()
    print('\n'.join(str(ans[i]+1) for i in aa))




testcase(1)
# testcase(int(inp()))


import sys
input = sys.stdin.buffer.readline
n = int(input())
a = list(map(int,input().split()))
n = max(a)+1
spf = [i for i in range(n)]
for i in range(4,n,2): spf[i] = 2
for i in range(3,int(n**.5)+1,2):
    if spf[i]!=i:continue
    for j in range(i*i, n, i):
        if spf[j]==j:spf[j] = i
cnt = 0
dp = [0]*n
for i in range(1,n):
    if spf[i]==i: cnt+=1
    dp[i] = cnt
def query(n):
    return dp[n]-dp[int(n**.5)]+1
print("\n".join(str(dp[n]-dp[int(n**.5)]+1) for n in a))


import sys
import os
from io import BytesIO, IOBase
BUFSIZE = 8192
class FastIO(IOBase):
    newlines = 0
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
################################# fast IO ###############################



input = sys.stdin.buffer.readline
n = int(input())
a = list(map(int,input().split()))
n = max(a)+1
spf = [i for i in range(n)]
for i in range(4,n,2): spf[i] = 2
for i in range(3,int(n**.5)+1,2):
    if spf[i]!=i:continue
    for j in range(i*i, n, i):
        if spf[j]==j:spf[j] = i
cnt = 0
dp = [0]*n
for i in range(1,n):
    if spf[i]==i: cnt+=1
    dp[i] = cnt
print("\n".join(str(dp[n]-dp[int(n**.5)]+1) for n in a))


import os,io
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
n = 10**6+1
primes = [1]*n
primes[0],primes[1] = 0,0
v = int(n**0.5)+1
for i in range(2,v):
    if primes[i]:
        for j in range(i*i,n,i):
            primes[j]=0
for i in range(1,n):
    primes[i]+=primes[i-1]

cases = int(input())
for t in range(cases):
    n1 = list(map(int,input().split()))
    for ni in n1:
        print(primes[ni]-primes[int(ni**0.5)]+1)