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