pythagorean-triplets-15

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

Source: hackerearth | Difficulty: MEDIUM
Tags: Mathematics


Solutions:
import math                                                                 

LIM = 10**6
PTHA = [set([]) for _ in range(LIM)]
PYTHA = [0] * LIM
MAX = int(LIM**0.5)


for m in range(1, MAX):
	for n in range(1, m):
		c, b, a = m*m + n*n, 2*m*n, m*m - n*n
		k = 1
		while k*c < LIM:
			tup = tuple(sorted([k*a, k*b, k*c]))
			PTHA[k*c].add(tup)
			# PYTHA[k*c] += 1
			k += 1


for i in range(1, len(PTHA)):
	PYTHA[i] += PYTHA[i - 1] + len(PTHA[i])


if __name__ == '__main__':
	for _ in range(int(input())):
		print(PYTHA[int(input())])