- All Contests
- ProjectEuler+
- Project Euler #138: Special isosceles triangles

# Project Euler #138: Special isosceles triangles

# Project Euler #138: Special isosceles triangles

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

Consider the isosceles triangle with base length, , and legs, .

By using the Pythagorean theorem it can be seen that the height of the triangle, , which is one less than the base length.

With and , , which is one more than the base length, and this is the second smallest isosceles triangle with the property that .

Given , find for the smallest isosceles triangles for which , are positive integers. Since this sum can be very large, output it modulo .

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

```
2
1
2
```

**Sample Output**

```
17
322
```