There are $N$ sabotages available in the game Among Us, initially all at level $0$. 
$N$ imposters are allotted the task to upgrade the level of the sabotages. 
The $i^{th}$ imposter $(1 \leq i \leq N)$ increases the level of $x^{th}$ sabotage $(1 \leq x \leq N)$ by one level  if $gcd(i,x)=i$.
You need to find the number of sabotages at LEVEL 5 after all the imposters have completed their tasks.

-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow. 
- Each testcase contains of a single line of input, one integer $N$. 

-----Output:-----
For each testcase, output in a single line the number of sabotages at LEVEL 5.

-----Constraints-----
- $1 \leq T \leq 10^5$
- $1 \leq N \leq 10^{18}$

-----Sample Input:-----
1
6

-----Sample Output:-----
0

-----EXPLANATION:-----
The $1^{st}$ sabotage is at level $1$, the $2^{nd}$, $3^{rd}$ and $5^{th}$ sabotages are at level $2$, the $4^{th}$ sabotage is at level $3$ and the $6^{th}$ sabotage is at level $4$.
None of them reach level $5$. Hence the output is $0$.

```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\r\nimport math\r\nfrom collections import defaultdict,Counter\r\nimport bisect\r\ninput=sys.stdin.readline\r\ndef print(x):\r\n    sys.stdout.write(str(x)+"\\n")\r\n\r\n# sys.stdout=open("CP1/output.txt",\'w\')\r\n# sys.stdin=open("CP1/input.txt",\'r\')\r\n\r\ndef Sieve(n):\r\n    prime = [True for i in range(n + 1)]\r\n    p = 2\r\n    while (p * p <= n):\r\n\t    if (prime[p] == True):\r\n\t\t    for i in range(p * p, n + 1, p):\r\n\t\t\t    prime[i] = False\r\n\t    p += 1\r\n    prime[0]= False\r\n    prime[1]= False\r\n\r\n    p1=[]\r\n    for p in range(n + 1):\r\n\t    if prime[p]:\r\n\t\t    p1.append(pow(p,4))\r\n    return p1\r\n\r\np=Sieve(10**5)\r\n# mod=pow(10,9)+7\r\nt=int(input())\r\nfor i in range(t):\r\n\tn=int(input())\r\n\tans=bisect.bisect_right(p,n)\r\n\tprint(ans)'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 1247814