Again Pythagoras

Time Limit: 1.5 sec

 

The Problem

In mathematics, the Pythagorean theorem, also known as Pythagoras' theorem, is a fundamental relation in Euclidean geometry among the three sides of a right triangle. It states that the square of the hypotenuse (the side opposite the right angle) is equal to the sum of the squares of the other two sides. The theorem can be written as an equation relating the lengths of the sides a, b and c, often called the "Pythagorean equation":  a² + b² = c²

 

The Pythagorean triplet (a,b,c) satisfies: 
a² + b² = c²

 

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.

 

The Input

First line contains T (1 <= T <= 100 ) , the number of test cases. Each test case consists of only one integer N (1 <= N <= 1000000)  in one line.

 

The Output

For each test case, print the required answer.

 

Sample Input

2

5

10

 

Sample Output

1

2

 

 

 

 

Online Practice Contest 2 [School & College Level]

Problem Setter: Parag Paul