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 = 'import os\nimport sys\nfrom io import BytesIO, IOBase\n# region fastio\nBUFSIZE = 8192\nclass FastIO(IOBase):\n    newlines = 0\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    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    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    def flush(self):\n        if self.writable:\n            os.write(self._fd, self.buffer.getvalue())\n            self.buffer.truncate(0), self.buffer.seek(0)\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")\nsys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)\ninput = lambda: sys.stdin.readline().rstrip("\\r\\n")\n\nMAXPRIME=10**6\nisPrime=[0 for _ in range(MAXPRIME+1)]\nisPrime[0]=-1;isPrime[1]=-1 #0 and 1 are not prime numbers\nfor i in range(2,MAXPRIME//2+1):\n    if isPrime[i]==0: #i is prime\n        for multiple in range(i*i,MAXPRIME+1,i):\n            if isPrime[multiple]==0:\n                isPrime[multiple]=i         \nprimeNumberSet=set()\nfor i in range(len(isPrime)):\n    if isPrime[i]==0:\n        primeNumberSet.add(i)\nprimes=sorted(list(primeNumberSet))\n\nlookupTable=[None for _ in range(MAXPRIME+1)]\n\npIdx=-1\npSqRtIdx=-1\nfor i in range(1,MAXPRIME+1):\n    while pIdx+1<len(primes) and primes[pIdx+1]<=i:\n        pIdx+=1\n    while pSqRtIdx+1<len(primes) and (primes[pSqRtIdx+1])**2<=i:\n        pSqRtIdx+=1\n    total=(pIdx+1)-(pSqRtIdx+1)+1 #1 is always lonely\n    lookupTable[i]=total\n\n#print(lookupTable[:30])\n\n#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\nt=int(input())\nn=[int(x) for x in input().split()]\nprint(\'\\n\'.join([str(lookupTable[nn]) for nn in n]))'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 54105141