Pythagorean triplet (a,b,c) satisfies: 
You will be given an integer N. You have to count how many triplets a,b,c exist such that  
1 ≤ a ≤ b ≤ c ≤ N.

Input: 
First line contains T, the number of testcases. Each testcase consists of only one integer in one line.    

Output: 
For each testcase, print the required answer.   

Constraints: 
1 ≤ T ≤ 100 
1 ≤ N ≤ 10^6

SAMPLE INPUT
2
5
10

SAMPLE OUTPUT
1
2

Explanation

In first testcase, only one triplet ie. (3,4,5)
In second testcase, two triplets ie. (3,4,5),(6,8,10).
tri = lambda m,n:(m**2-n**2, 2*m*n, m**2+n**2)

def coprime(x, y):
	while y:
		x, y = y, x%y
	return x==1

n = input()
while n:
	n -= 1
	
	m = input()
	c, i = 0, 2
	l = int(pow(m,0.5)) + 1
	while i<l:
		j = 1
		while j<i:
			if coprime(i,j) and (i**2+j**2)<=m and (i-j)%2:
				c += m/(i**2+j**2)
			j += 1
		i += 1
	print c