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.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = '"""\n    Author - Satwik Tiwari .\n    27th Sept , 2020  - Sunday\n"""\n\n#===============================================================================================\n#importing some useful libraries.\n\n\n\nfrom fractions import Fraction\nimport sys\nimport os\nfrom io import BytesIO, IOBase\n\n\n# from itertools import *\nfrom heapq import *\n# from math import gcd, factorial,floor,ceil\n\nfrom copy import deepcopy\nfrom collections import deque\n\n\n# from collections import Counter as counter  # Counter(list)  return a dict with {key: count}\n# from itertools import combinations as comb # if a = [1,2,3] then print(list(comb(a,2))) -----> [(1, 2), (1, 3), (2, 3)]\n# from itertools import permutations as permutate\n\n\nfrom bisect import bisect_left as bl\nfrom bisect import bisect_right as br\nfrom bisect import bisect\n\n#==============================================================================================\n#fast I/O region\nBUFSIZE = 8192\n\n\nclass FastIO(IOBase):\n    newlines = 0\n\n    def __init__(self, file):\n        self._fd = file.fileno()\n        self.buffer = BytesIO()\n        self.writable = "x" in file.mode or "r" not in file.mode\n        self.write = self.buffer.write if self.writable else None\n\n    def read(self):\n        while True:\n            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n            if not b:\n                break\n            ptr = self.buffer.tell()\n            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)\n        self.newlines = 0\n        return self.buffer.read()\n\n    def readline(self):\n        while self.newlines == 0:\n            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n            self.newlines = b.count(b"\\n") + (not b)\n            ptr = self.buffer.tell()\n            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)\n        self.newlines -= 1\n        return self.buffer.readline()\n\n    def flush(self):\n        if self.writable:\n            os.write(self._fd, self.buffer.getvalue())\n            self.buffer.truncate(0), self.buffer.seek(0)\n\n\nclass IOWrapper(IOBase):\n    def __init__(self, file):\n        self.buffer = FastIO(file)\n        self.flush = self.buffer.flush\n        self.writable = self.buffer.writable\n        self.write = lambda s: self.buffer.write(s.encode("ascii"))\n        self.read = lambda: self.buffer.read().decode("ascii")\n        self.readline = lambda: self.buffer.readline().decode("ascii")\n\n\ndef print(*args, **kwargs):\n    """Prints the values to a stream, or to sys.stdout by default."""\n    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)\n    at_start = True\n    for x in args:\n        if not at_start:\n            file.write(sep)\n        file.write(str(x))\n        at_start = False\n    file.write(kwargs.pop("end", "\\n"))\n    if kwargs.pop("flush", False):\n        file.flush()\n\n\nif sys.version_info[0] < 3:\n    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)\nelse:\n    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)\n\n# inp = lambda: sys.stdin.readline().rstrip("\\r\\n")\n\n#===============================================================================================\n### START ITERATE RECURSION ###\nfrom types import GeneratorType\ndef iterative(f, stack=[]):\n  def wrapped_func(*args, **kwargs):\n    if stack: return f(*args, **kwargs)\n    to = f(*args, **kwargs)\n    while True:\n      if type(to) is GeneratorType:\n        stack.append(to)\n        to = next(to)\n        continue\n      stack.pop()\n      if not stack: break\n      to = stack[-1].send(to)\n    return to\n  return wrapped_func\n#### END ITERATE RECURSION ####\n\n#===============================================================================================\n#some shortcuts\n\nmod = 10**9+7\ndef inp(): return sys.stdin.readline().rstrip("\\r\\n") #for fast input\ndef out(var): sys.stdout.write(str(var))  #for fast output, always take string\ndef lis(): return list(map(int, inp().split()))\ndef stringlis(): return list(map(str, inp().split()))\ndef sep(): return list(map(int, inp().split()))\ndef strsep(): return list(map(str, inp().split()))\n# def graph(vertex): return [[] for i in range(0,vertex+1)]\ndef zerolist(n): return [0]*n\ndef nextline(): out("\\n")  #as stdout.write always print sring.\ndef testcase(t):\n    for pp in range(t):\n        solve(pp)\ndef printlist(a) :\n    for p in range(0,len(a)):\n        out(str(a[p]) + \' \')\ndef google(p):\n    print(\'Case #\'+str(p)+\': \',end=\'\')\ndef lcm(a,b): return (a*b)//gcd(a,b)\ndef power(x, y, p) :\n    res = 1     # Initialize result\n    x = x % p  # Update x if it is more , than or equal to p\n    if (x == 0) :\n        return 0\n    while (y > 0) :\n        if ((y & 1) == 1) : # If y is odd, multiply, x with result\n            res = (res * x) % p\n\n        y = y >> 1      # y = y/2\n        x = (x * x) % p\n    return res\ndef ncr(n,r): return factorial(n) // (factorial(r) * factorial(max(n - r, 1)))\ndef isPrime(n) :\n    if (n <= 1) : return False\n    if (n <= 3) : return True\n    if (n % 2 == 0 or n % 3 == 0) : return False\n    i = 5\n    while(i * i <= n) :\n        if (n % i == 0 or n % (i + 2) == 0) :\n            return False\n        i = i + 6\n    return True\n\n#===============================================================================================\n# code here ;))\nans = [0]*(10**6+5)\n\ndef sieve(a): #O(n loglogn) nearly linear\n    #all odd mark 1\n    for i in range(3,((10**6)+5),2):\n        a[i] = 1\n    #marking multiples of i form i*i 0. they are nt prime\n    for i in range(3,((10**6)+5),2):\n        for j in range(i*i,((10**6)+5),i):\n            a[j] = 0\n    a[2] = 1 #special left case\n    return (a)\n\n\na = [0]*((10**6)+6)\na = sieve(a)\nprimes = []\nfor i in range(10**6+1):\n    if(a[i]):\n        primes.append(i)\n\n# primes = primes[1:]\n# print(ans[:20])\n\n\nfor i in primes:\n    ans[i] += 1\n    ans[min(10**6+2,i*i)] -=1\n\n# print(ans[:20])\nfor i in range(2,10**6+1):\n    ans[i] +=ans[i-1]\n\n# print(ans[:20])\n\n\ndef solve(case):\n    n = int(inp())\n    aa = lis()\n    print(\'\\n\'.join(str(ans[i]+1) for i in aa))\n\n\n\n\ntestcase(1)\n# testcase(int(inp()))\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 51282730