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: UNKNOWN_DIFFICULTY

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))


from math import sqrt
t = int(input())

def isprime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	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')

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)
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)