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 = '# ------------------- fast io --------------------\nimport os\nimport sys\nfrom io import BytesIO, IOBase\n \nBUFSIZE = 8192\n \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 \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 \nsys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)\ninput = lambda: sys.stdin.readline().rstrip("\\r\\n")\n# ------------------- fast io --------------------\nfrom bisect import bisect_left as bsl;import math\ndef sieve(n): \n    prime = [True for i in range(n + 1)] \n    p = 2\n    while (p * p <= n): \n        if (prime[p] == True): \n            for i in range(p * 2, n + 1, p): \n                prime[i] = False\n        p += 1\n    prime[0]= False\n    prime[1]= False\n    pp=[]\n    for p in range(n + 1): \n        if prime[p]: \n            pp.append(p)\n    return pp\nprimes=sieve(10**6)\nt=int(input());vals=list(map(int,input().split()))\nfor j in range(t):\n    n=vals[j]\n    ind1=min(bsl(primes,math.floor(math.sqrt(n))),len(primes)-1)\n    ind2=min(bsl(primes,n),len(primes)-1)\n    if primes[ind1]>math.floor(math.sqrt(n)):\n        ind1-=1\n    if primes[ind2]>n:\n        ind2-=1\n    print(ind2+1-ind1)'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 11606038