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$.

Difficulty: interview

Starter code:

Solutions:
from bisect import bisect
n = 32000
def primeSeive(n):
    prime = [True for i in range(n + 1)]
    primes = []
    p = 2
    while (p * p <= n):
        if (prime[p] == True):
            for i in range(p * 2, n + 1, p):
                prime[i] = False
        p += 1
    prime[0] = False
    prime[1] = False
    for p in range(n + 1):
        if prime[p]:
            primes.append(p)
    return primes
arr = primeSeive(n)
fin = []
for i in arr:
    fin.append(pow(i,4))
for _ in range(int(input())):
    n = int(input())
    print(bisect(fin,n))


# cook your dish here
from math import sqrt
t=int(input())
def isprime(n) : 
 
    # Corner cases 
    if (n <= 1) : 
        return False
    if (n <= 3) : 
        return True
 
    # This is checked so that we can skip 
    # middle five numbers in below loop 
    if (n % 2 == 0 or n % 3 == 0) : 
        return False
 
    i = 5
    while(i * i <= n) : 
        if (n % i == 0 or n % (i + 2) == 0) : 
            return False
        i = i + 6
 
    return True
   
d={}
for i in range(2,100000):
    d[i]=isprime(i)
l= [i for i in d.keys() if d[i]==True]
for _ in range(t):
    n=int(input())
    s=0
    e=len(l)-1
    ans=-1
    while(s<=e):
        mid=(s+e)//2
        if((l[mid]**4)<=n):
            ans=mid
            s=mid+1;
        else:
            e=mid-1
    print(ans+1)

import sys
import math
from collections import defaultdict,Counter
import bisect
input=sys.stdin.readline
def print(x):
    sys.stdout.write(str(x)+"\n")

# sys.stdout=open("CP1/output.txt",'w')
# sys.stdin=open("CP1/input.txt",'r')

def Sieve(n):
    prime = [True for i in range(n + 1)]
    p = 2
    while (p * p <= n):
	    if (prime[p] == True):
		    for i in range(p * p, n + 1, p):
			    prime[i] = False
	    p += 1
    prime[0]= False
    prime[1]= False

    p1=[]
    for p in range(n + 1):
	    if prime[p]:
		    p1.append(pow(p,4))
    return p1

p=Sieve(10**5)
# mod=pow(10,9)+7
t=int(input())
for i in range(t):
	n=int(input())
	ans=bisect.bisect_right(p,n)
	print(ans)

from sys import stdin, stdout
from math import ceil, floor, gcd, fabs, factorial, fmod, sqrt, inf
from bisect import bisect_left as bl, bisect_right as br, bisect
mod = pow(10, 9) + 7
mod2 = 998244353
def inp(): return stdin.readline().strip()
def out(var, end="\n"): stdout.write(str(var)+"\n")
def outa(*var, end="\n"): stdout.write(' '.join(map(str, var)) + end)
def lmp(): return list(mp())
def mp(): return list(map(int, inp().split()))
def smp(): return list(map(str, inp().split()))
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]
def remadd(x, y): return 1 if x%y else 0

def chkprime(x):
    if x<=1: return False
    if x in (2, 3): return True
    if x%2 == 0: return False
    for i in range(3, int(sqrt(x))+1, 2):
        if x%i == 0: return False
    return True

l = []
i = 2
while True:
    if i**4 > 10**18: break
    if chkprime(i):
        l.append(i**4)
    i += 1

for _ in range(int(inp())):
    n = int(inp())
    k = br(l, n)
    print(k)