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 sys\ninput=sys.stdin.buffer.readline #FOR READING PURE INTEGER INPUTS (space separation ok)\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()]\nfor nn in n:\n    print(lookupTable[nn])\n\n\n\n\n#def gcd(x, y):\n#    while y != 0:\n#        (x, y) = (y, x % y)\n#    return x\n#lonely=[]\n#for i in range(1,n+1):\n#    ok=False\n#    for j in range(1,n+1):\n#        g=gcd(i,j)\n#        a=g\n#        b=i//g\n#        c=j//g\n#        if a+b>c and b+c>a and a+c>b:\n#            ok=True\n#            if i in primeNumberSet:\n#                print(i,j)\n#            break\n#    if ok==False:\n#        lonely.append(i)\n#print(lonely)\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 54087994