import math
import bisect
big_N = 10**7
N = 3164 #sqrt(10**7)
Primes = [True]*N
for i in range(2, int(N**0.5)):
    if Primes[i] == True:
        for j in range(i * i, int(N), i):
            Primes[j] = False
Primes[0] = Primes[1] = False
sum_list = set()

for i in range(2, math.ceil(math.sqrt(big_N))):
    for j in range(2, math.ceil(big_N ** (1/3))):
        for k in range(2, math.ceil(big_N ** (1/4))):
            if Primes[i] and Primes[j] and Primes[k]:
                # print(i, j, k)
                Sum = i**2 + j**3 + k**4
                if Sum > big_N:
                    break
                sum_list.add(Sum) 
sums = list(sum_list)
sums.sort()

for i in range(int(input())):
    n = int(input())
    print(bisect.bisect_right(sums, n))