- All Contests
- ProjectEuler+
- Project Euler #139: Pythagorean tiles

# Project Euler #139: Pythagorean tiles

# 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**

```
1
```