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
1