Project Euler #139: Pythagorean tiles

_{This problem is a programming version of Problem 139 from projecteuler.net}

Let represent the three sides of a right angle triangle with integral length sides. It is possible to place four such triangles together to form a square with length .

For example, triangles can be placed together to form a by square with a by hole in the middle and it can be seen that the by square can be tiled with twenty-five by squares.

However, if triangles were used then the hole would measure by and these could not be used to tile the by square.

Given , how many Pythagorean triangles would allow such a tiling to take place and whose perimeter is less than ?

Input Format

The first line of input contains , the number of test cases.

Each test case consists of a single line containing a single integer, .

Constraints

In the first test case:
In the second test case:
In the third test case:

Output Format

For each test case, output a single line containing a single integer, the answer for that test case.

Sample Input

1
15

Sample Output