Find the count of numbers less than equal to N having exactly 9 divisors.
 
Example 1:
Input:
N = 100
Output:
2
Explanation:
The two numbers which have 
exactly 9 divisors are 36 and 100.
Example 2:
Input:
N = 1000
Output:
8 
Explanation:
The numbers are:
36 100 196 225 256 441 484 676
Your Task:  
You don't need to read input or print anything. Your task is to complete the function nineDivisors() which takes an integer N as an input parameter and returns the total number of elements from 1 to N inclusive, that have exactly 9 divisors.
Expected Time Complexity: O(sqrt(Nlog(logN)))
Expected Auxiliary Space:  O(sqrt(N))
 
Constraints:
1<=N<=10^{10}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Number theory

Sorting

Complete search

Starter code: #User function Template for python3

class Solution:

    def nineDivisors(self, N):

        # code here 

Solutions:
class Solution:

	def nineDivisors(self, n):
		c = 0
		limit = int(n ** 0.5)
		prime = [i for i in range(limit + 1)]
		i = 2
		while i * i <= limit:
			if prime[i] == i:
				for j in range(i * i, limit + 1, i):
					if prime[j] == j:
						prime[j] = i
			i += 1
		for i in range(2, limit + 1):
			p = prime[i]
			q = prime[i // prime[i]]
			if p * q == i and q != 1 and (p != q):
				c += 1
			elif prime[i] == i:
				if i ** 8 <= n:
					c += 1
		return c


class Solution:

	def nineDivisors(self, N):

		def SieveOfEratosthenes(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
			x = []
			for p in range(2, n + 1):
				if prime[p]:
					x.append(p)
			return x
		s = int(N ** 0.5)
		p = SieveOfEratosthenes(s)
		t = 0
		for i in range(len(p)):
			if p[i] ** 4 <= s:
				t += 1
			for j in range(i + 1, len(p)):
				if p[i] * p[j] <= s:
					t += 1
				else:
					break
		return t


import math
import bisect

class Solution:

	def nineDivisors(self, N):
		sN = int(math.sqrt(N))
		prime = [True] * (sN + 1)
		for i in range(2, int(math.sqrt(sN)) + 1):
			if prime[i]:
				for j in range(i * i, sN + 1, i):
					prime[j] = False
		primes = []
		for i in range(2, sN + 1):
			if prime[i]:
				primes.append(i)
		primesSize = len(primes)
		ans = 0
		for i in range(primesSize):
			notExceed = int(math.sqrt(N)) // primes[i]
			ans += bisect.bisect(primes, notExceed, 0, i)
		for i in range(primesSize):
			sq = primes[i] * primes[i]
			if sq * sq * sq * sq <= N:
				ans += 1
			else:
				break
		return ans


class Solution:

	def nineDivisors(self, n):
		res = int(n ** 0.5)
		ar = [i for i in range(res + 1)]
		for i in range(2, res + 1):
			if ar[i] == i:
				for j in range(i * i, res + 1, i):
					if ar[j] == j:
						ar[j] = i
		ans = 0
		for i in range(2, res + 1):
			p = ar[i]
			q = ar[i // ar[i]]
			if p * q == i and p != q and (q != 1):
				ans += 1
			elif ar[i] == i and i ** 8 < n:
				ans += 1
		return ans

	def factors(self, n):
		num = n * n
		ans = 0
		i = 1
		while i <= n:
			if num % i == 0:
				ans += 2
			if i * i == num:
				ans -= 1
			i += 1
		return ans


import math

class Solution:

	def nineDivisors(self, N):
		sq = int(math.sqrt(N)) + 1
		list1 = [0] * (sq + 1)
		list1[1] = -1
		prime = []
		count = 0
		p = 2
		while p * p <= sq:
			if list1[p] == 0:
				for j in range(p * p, sq + 1, p):
					list1[j] = -1
			p += 1
		for i in range(2, sq + 1, 1):
			if list1[i] == 0:
				prime.append(i)
		pn = len(prime)
		for i in range(pn):
			if prime[i] ** 8 <= N:
				count += 1
			if (prime[i] * prime[i + 1]) ** 2 <= N:
				count += 1
			else:
				break
			for j in range(i + 2, pn):
				if (prime[i] * prime[j]) ** 2 <= N:
					count += 1
				else:
					break
		return count


import math

def sieve(n):
	prime = []
	isprime = [True for i in range(n + 1)]
	spf = [-1 for i in range(n + 1)]
	l = 0
	for i in range(2, n + 1):
		if isprime[i]:
			prime.append(i)
			l += 1
			spf[i] = i
		j = 0
		while j < l and prime[j] <= spf[i] and (prime[j] * i <= n):
			isprime[prime[j] * i] = False
			spf[i * prime[j]] = prime[j]
			j += 1
	return prime

class Solution:

	def nineDivisors(self, N):
		n = int(N ** 0.5)
		prime = sieve(n)
		l = len(prime)
		v = int(N ** 0.125)
		c = 0
		for i in prime:
			if i > v:
				break
			c += 1
		j = l - 1
		for i in range(l):
			while j > i:
				if (prime[i] * prime[j]) ** 2 <= N:
					c += j - i
					break
				j -= 1
		return c
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.nineDivisors(N))


class Solution:

	def nineDivisors(self, n):
		c = 0
		limit = int(n ** 0.5)
		prime = [i for i in range(limit + 1)]
		i = 2
		while i * i <= limit:
			if prime[i] == i:
				for j in range(i * i, limit + 1, i):
					if prime[j] == j:
						prime[j] = i
			i += 1
		for i in range(2, limit + 1):
			p = prime[i]
			q = prime[i // prime[i]]
			if p * q == i and q != 1 and (p != q):
				c += 1
			elif prime[i] == i:
				if i ** 8 <= n:
					c += 1
		return c
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.nineDivisors(N))


import math

class Solution:

	def nineDivisors(self, N):
		prime_nos = []
		for i in range(int(math.sqrt(N)) + 1):
			prime_nos.append(i)
		j = 2
		while j * j < int(math.sqrt(N)) + 1:
			if prime_nos[j] == j:
				k = j * j
				while k < int(math.sqrt(N)) + 1:
					if prime_nos[k] == k:
						prime_nos[k] = j
					k += j
			j += 1
		c = 0
		for i in range(2, int(math.sqrt(N)) + 1):
			p = prime_nos[i]
			q = prime_nos[i // p]
			if p != q and p * q == i and (q != 1) or (prime_nos[i] == i and i ** 8 <= N):
				c += 1
		return c
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.nineDivisors(N))


import math

class Solution:

	def nineDivisors(self, N):
		limit = int(math.sqrt(N))
		prime = [i for i in range(limit + 1)]
		i = 2
		while i * i <= limit:
			if prime[i] == i:
				for j in range(i * i, limit + 1, i):
					if prime[j] == j:
						prime[j] = i
			i += 1
		count = 0
		for i in range(2, limit + 1):
			p = prime[i]
			q = prime[i // prime[i]]
			if p * q == i and q != 1 and (p != q):
				count += 1
			elif prime[i] == i:
				if i ** 8 <= N:
					count += 1
		return count
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.nineDivisors(N))


class Solution:

	def nineDivisors(self, n):
		res = int(n ** 0.5)
		ar = [i for i in range(res + 1)]
		for i in range(2, res + 1):
			if ar[i] == i:
				for j in range(i * i, res + 1, i):
					if ar[j] == j:
						ar[j] = i
		ans = 0
		for i in range(2, res + 1):
			p = ar[i]
			q = ar[i // ar[i]]
			if p * q == i and p != q and (q != 1):
				ans += 1
			elif ar[i] == i and i ** 8 < n:
				ans += 1
		return ans

	def factors(self, n):
		num = n * n
		ans = 0
		i = 1
		while i <= n:
			if num % i == 0:
				ans += 2
			if i * i == num:
				ans -= 1
			i += 1
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.nineDivisors(N))


import math

def divisor(x, arr):
	i = 1
	while i * i <= x:
		if x % i == 0:
			arr.add(i)
			arr.add(x // i)
		i += 1

def count(i, val, primes):
	l = 0
	h = i - 1
	ans = i
	while l <= h:
		mid = (l + h) // 2
		if primes[mid] <= val:
			l = mid + 1
		else:
			h = mid - 1
			ans = mid
	return ans

class Solution:

	def nineDivisors(self, n):
		sqn = int(math.sqrt(n))
		prime = [1 for i in range(sqn + 1)]
		i = 2
		c = 0
		while i <= sqn:
			if prime[i]:
				for j in range(i * i, sqn + 1, i):
					prime[j] = 0
			i += 1
		primes = []
		for p in range(2, len(prime)):
			if prime[p]:
				primes.append(p)
		for i in range(len(primes)):
			val = sqn // primes[i]
			c += count(i, val, primes)
		for i in primes:
			sq = i * i
			if sq ** 4 <= n:
				c += 1
			else:
				break
		return c
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.nineDivisors(N))


class Solution:

	def nineDivisors(self, N):
		root = int(N ** 0.5)
		prime = [0] * (root + 1)
		count = 0
		for i in range(1, root + 1):
			prime[i] = i
		for i in range(2, root + 1):
			if i * i > root:
				break
			if prime[i] != i:
				continue
			for j in range(i * i, root + 1, i):
				if prime[j] == j:
					prime[j] = prime[i]
		for i in range(2, root + 1):
			p = prime[i]
			q = prime[i // prime[i]]
			if p * q == i and q != 1 and (p != q):
				count += 1
			elif prime[i] == i and i ** 8 <= N:
				count += 1
		return count
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.nineDivisors(N))


class Solution:

	def countdiv(self, n):
		limit = int(n ** 0.5)
		skip = 2
		conta = 1
		check = 3
		if n % 2 == 0:
			skip = 1
			conta = 2
		while check < limit:
			if n % check == 0:
				conta = conta + 1
			check = check + skip
			if conta > 4:
				return False
		if conta == 4:
			return True
		else:
			False

	def prime_factors(self, n):
		i = 2
		while i * i <= n:
			if n % i:
				i += 1
			else:
				return 1
		return 0

	def nineDivisors(self, N):
		conta = 0
		check = False
		primi = [2]
		pos = 0
		limit = int(N ** 0.5)
		for i in range(3, limit + 1):
			if self.prime_factors(i) == 0:
				while pos >= 0:
					if primi[pos] * i > limit:
						check = True
						pos -= 1
					else:
						break
				conta = conta + pos + 1
				primi.append(i)
				if not check:
					pos = len(primi) - 1
		pos = 0
		while primi[pos] ** 8 <= N:
			conta += 1
			pos += 1
		return conta
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.nineDivisors(N))


import math

class Solution:

	def sieve(self, isPrime, n):
		isPrime[0] = False
		isPrime[1] = False
		for i in range(2, int(math.sqrt(n) + 1)):
			if isPrime[i]:
				for j in range(i ** 2, int(n + 1), i):
					isPrime[j] = False

	def binary_search(self, n, cannotExceedValue, prime):
		low = 0
		high = n - 1
		ans = 0
		while low <= high:
			mid = low + high >> 1
			if prime[mid] <= cannotExceedValue:
				low = mid + 1
				ans = mid + 1
			else:
				high = mid - 1
		return ans

	def nineDivisors(self, N):
		m = math.sqrt(N)
		isPrime = [True] * int(m + 1)
		self.sieve(isPrime, m)
		prime = []
		for i in range(int(m + 1)):
			if isPrime[i]:
				prime.append(i)
		n = len(prime)
		ans = 0
		for i in range(n - 1, -1, -1):
			prime1 = prime[i]
			cannotExceedValue = int(m / prime1)
			ans += self.binary_search(i, cannotExceedValue, prime)
		for i in prime:
			if int(i ** 8) <= N:
				ans += 1
		return ans


class PrimeNumbers:

	def prime_numbers(lower, upper, plist, slist):
		for num in range(lower, upper + 1):
			if num > 1:
				for i in range(2, num):
					if num % i == 0:
						break
				else:
					plist.append(num)
					slist.append(num * num)

class Solution:

	def nineDivisors(self, N):
		c = 0
		limit = int(N ** 0.5)
		prime = [i for i in range(limit + 1)]
		i = 2
		while i * i <= limit:
			if prime[i] == i:
				for j in range(i * i, limit + 1, i):
					if prime[j] == j:
						prime[j] = i
			i += 1
		for i in range(2, limit + 1):
			p = prime[i]
			q = prime[i // prime[i]]
			if p * q == i and q != 1 and (p != q):
				c += 1
			elif prime[i] == i:
				if i ** 8 <= N:
					c += 1
		return c

	def nineDivisors_gen(self, N):
		primes = []
		squares = []
		PrimeNumbers.prime_numbers(0, 2000, primes, squares)
		epower = [2 ** 8, 3 ** 8, 5 ** 8, 7 ** 8, 11 ** 8, 13 ** 8, 17 ** 8]
		divisors = 0
		i = 0
		while i < len(squares) - 1 and squares[i] * squares[i + 1] <= N:
			j = i + 1
			while j < len(squares) and squares[i] * squares[j] <= N:
				divisors += 1
				j += 1
			i += 1
		i = 0
		while i < len(epower) and epower[i] <= N:
			divisors += 1
			i += 1
		return divisors
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.nineDivisors(N))


class Solution:

	def isprime(self, n):
		if n < 2:
			return False
		if n == 3 or n == 2 or n == 5:
			return True
		if n % 2 == 0 or n % 3 == 0 or n % 5 == 0:
			return False
		for i in range(5, int(n ** 0.5) + 1, 6):
			if n % (i + 2) == 0 or n % (i + 6) == 0:
				return False
		return True

	def nineDivisors(self, N):
		if N < 36:
			return 0
		prime = []
		for i in range(2, int(N ** 0.5) + 1):
			if self.isprime(i):
				prime.append(i)
		count = 0
		for i in range(len(prime)):
			x = prime[i]
			if x ** 8 <= N:
				count += 1
			else:
				break
		for i in range(len(prime) - 1):
			x = prime[i]
			flag = True
			l = i + 1
			h = len(prime) - 1
			while l <= h:
				mid = (l + h) // 2
				if x * x * prime[mid] ** 2 <= N:
					count += mid - l + 1
					l = mid + 1
					flag = False
				else:
					h = mid - 1
			if flag:
				break
		return count
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.nineDivisors(N))


class Solution:

	def find_prime(self, num):
		arr = [i for i in range(num)]
		for i in range(2, num):
			if arr[i] == i:
				j = i
				while j < num:
					if arr[j] == j:
						arr[j] = i
					j = j + i
		return arr

	def nineDivisors(self, N):
		count = 0
		prime = self.find_prime(int(N ** 0.5 + 1))
		for i in range(2, int(N ** 0.5) + 1):
			a = prime[i]
			b = prime[i // a]
			if a != b and b != 1 and (a * b == i) or (prime[i] == i and i ** 8 <= N):
				count += 1
		return count
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.nineDivisors(N))


class Solution:

	def nineDivisors(self, n):
		l = [1] * (int(n ** 0.5) + 1)
		(l[0], l[1]) = (0, 0)
		x = len(l)
		for i in range(2, int(x ** 0.5) + 1):
			if l[i] == 1:
				for j in range(i * i, x, i):
					l[j] = 0
		c = 0
		for i in range(2, x):
			if l[i] == 1:
				if (i * i) ** 2 > n:
					break
				for j in range(i, x):
					if l[j] == 1:
						if i == j:
							a = i * i
							a = a * a
							a = a * a
							if a <= n:
								c += 1
						else:
							a = i * j
							a *= a
							if a <= n:
								c += 1
							else:
								break
		return c
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.nineDivisors(N))


class Solution:

	def nineDivisors(self, N):
		ans = 0
		k = int(N ** 0.5)
		l = [0] * (k + 1)
		for i in range(1, k + 1):
			l[i] = i
		i = 2
		while i * i <= k:
			if l[i] == i:
				for j in range(i + i, k + 1, i):
					if l[j] == j:
						l[j] = i
			i += 1
		for i in range(2, k + 1):
			p = l[i]
			q = l[int(i / p)]
			if p != q and p * q == i and (q != 1) or (l[i] == i and i ** 8 <= N):
				ans += 1
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.nineDivisors(N))


class Solution:

	def nineDivisors(self, N):
		count = 0
		high = int(N ** 0.5)
		sieve = [i for i in range(high + 1)]
		i = 2
		while i * i <= high:
			if sieve[i] == i:
				for j in range(i * i, high + 1, i):
					if sieve[j] == j:
						sieve[j] = i
			i += 1
		for i in range(2, high + 1):
			p = sieve[i]
			q = sieve[i // sieve[i]]
			if p * q == i and q != 1 and (p != q):
				count += 1
			elif sieve[i] == i:
				if i ** 8 <= N:
					count += 1
		return count
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.nineDivisors(N))


import math

class Solution:

	def nineDivisors(self, N):
		size = int(math.sqrt(N))
		prime = [0] * (size + 1)
		for i in range(len(prime)):
			prime[i] = i
		for i in range(2, size + 1):
			if prime[i] == i:
				n = 1
				while i * n < size + 1:
					prime[i * n] = i
					n += 1
		cnt = 0
		for k in range(2, size + 1):
			p = prime[k]
			q = prime[k // p]
			if p != q and p * q == k and (q != 1) or (prime[k] == k and k ** 8 <= N):
				cnt += 1
		return cnt


N = 150000
dp = [0 for i in range(150000)]
primes = []
primes2 = []
for i in range(2, 150000):
	for j in range(i * i, 150000, i):
		dp[j] = 1
	if not dp[i]:
		primes.append(i)
		primes2.append(i * i)

def bs(i, j, k):
	if i > j:
		return j
	m = (i + j) // 2
	if k < primes2[m]:
		return bs(i, m - 1, k)
	return bs(m + 1, j, k)

class Solution:

	def nineDivisors(self, N):
		s = 0
		for p in primes2:
			if p ** 4 <= N:
				s += 1
			else:
				break
		for p in primes2:
			if p * 4 > N:
				break
			x = bs(0, len(primes2) - 1, min(N / p, p - 1))
			s += x + 1
		return s
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.nineDivisors(N))


from math import sqrt

class Solution:

	def nineDivisors(self, N):
		size = int(sqrt(N))
		sieve = [i for i in range(size + 1)]
		for i in range(2, size + 1):
			if sieve[i] == i:
				j = i * 2
				while j < size + 1:
					sieve[j] = i
					j += i
		res = 0
		for i in range(2, size + 1):
			p = sieve[i]
			q = sieve[i // p]
			if p != q and p * q == i and (q != 1):
				res += 1
			if sieve[i] == i and i ** 8 < N:
				res += 1
		return res
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.nineDivisors(N))


primes = [2]
prime = [1] * 100001
for i in range(4, 100001, 2):
	prime[i] = 0
for i in range(3, 100001, 2):
	if prime[i]:
		for j in range(i * i, 100001, i):
			prime[j] = 0
		primes.append(i)
m = len(primes)

class Solution:

	def nineDivisors(self, n):
		ans = 0
		for i in range(m):
			x = primes[i] * primes[i]
			if x >= n:
				break
			if pow(x, 4) <= n:
				ans += 1
			l = 0
			r = i - 1
			while l <= r:
				mid = (l + r) // 2
				z = primes[mid] * primes[mid] * x
				if z <= n:
					l = mid + 1
				else:
					r = mid - 1
			ans += l
		return ans


class Solution:

	def nineDivisors(self, N):
		t = 0
		s = int(pow(N, 0.5)) + 1
		primes = [1 for i in range(s)]
		arr = []
		for i in range(2, s):
			if primes[i] and i != 1:
				arr.append(i)
				for j in range(i + i, s, i):
					primes[j] = 0
		t = 0
		for i in range(len(arr)):
			for j in range(i + 1, len(arr)):
				if arr[i] * arr[j] < s:
					t += 1
				else:
					break
		for i in arr:
			if i ** 8 <= N:
				t += 1
			else:
				break
		return t
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.nineDivisors(N))


class Solution:

	def nineDivisors(self, N):
		k = int(N ** 0.5)
		primes = [1 for i in range(k + 1)]
		primes[0] = 0
		primes[1] = 0
		for i in range(2, k + 1):
			if primes[i]:
				for j in range(i * i, k + 1, i):
					primes[j] = 0
		curr = []
		for i in range(len(primes)):
			if not curr:
				curr.append(primes[i])
			else:
				curr.append(curr[-1] + primes[i])
		res = 0
		for i in range(int(len(primes))):
			if primes[i]:
				a = int(N ** 0.5 / i)
				res += max(curr[a] - curr[i], 0)
		res += curr[int(N ** (1 / 8))]
		return res
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.nineDivisors(N))


import math

class Solution:

	def nineDivisors(self, N):
		ans = 0
		p = [2, 3, 5, 7, 11, 13, 17, 19]
		for i in p:
			if i ** 8 <= N:
				ans += 1
			else:
				break
		prime = [1] * (math.ceil(math.sqrt(N)) + 1)
		n = math.ceil(math.sqrt(N))
		for i in range(2, n):
			if prime[i] == 1:
				j = 2
				while i * j <= n:
					prime[i * j] = 0
					j += 1
		final = []
		for i in range(2, n + 1):
			if prime[i] == 1:
				final.append(i)
		for i in range(len(final)):
			for j in range(i + 1, len(final)):
				if final[i] * final[j] * final[i] * final[j] <= N:
					ans += 1
				else:
					break
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.nineDivisors(N))


import math

class Solution:
	Primes = []

	def nineDivisors(self, N):
		upto = int(math.sqrt(N))
		self.SieveOfEratosthenes(upto)
		counter = 0
		for j in range(2, upto + 1):
			p = self.Primes[j]
			q = self.Primes[j // self.Primes[j]]
			if p * q == j and p != q and (q != 1):
				counter += 1
			elif p == j and j ** 8 <= N:
				counter += 1
		return counter

	def SieveOfEratosthenes(self, n):
		self.Primes = [i for i in range(n + 1)]
		i = 2
		while i * i <= n:
			if self.Primes[i] == i:
				for j in range(i * i, n + 1, i):
					if self.Primes[j] == j:
						self.Primes[j] = i
			i += 1


import math

class Solution:

	def nineDivisors(self, N):
		n = int(math.sqrt(N))
		p = 2
		prime = [True for i in range(n + 1)]
		while p * p <= n:
			if prime[p]:
				for i in range(p * p, n + 1, p):
					prime[i] = False
			p += 1
		arr = []
		for i in range(2, n + 1):
			if prime[i]:
				arr.append(i)
		ans = 0
		power = [i * i for i in arr]
		i = 0
		j = len(arr) - 1
		while i < j:
			if power[i] * power[j] <= N:
				ans += j - i
				i += 1
			else:
				j -= 1
		for i in arr:
			if i ** 8 <= N:
				ans += 1
			else:
				break
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.nineDivisors(N))