import math
x = (5*(10**5))+1
prime_list = [0 for i in range(x)]
prime_list[0] = prime_list[1]= 1
for i in range(2, ((5*(10**5))//2)+1):
    if prime_list[i] == 0:
        for j in range(i**2, ((5*(10**5))//2)+1, i):
            prime_list[j] = 1
prime = [i for i in range(x) if prime_list[i]==0]

for i in range(int(input())):
    n = int(input().strip())
    count = 0
    if n<=2 or n% 2==0:
        print(0)
    else:
        index = 0
        p = prime[0]
        while p < n:
            ans1 = (n-p)/2
            ans2 = math.modf(math.sqrt(ans1))
           
            if ans2[0] == 0.0:
                count+=1
            index+=1
            p = prime[index]
            
        print(count)