Project Euler #39: Integer right triangles

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

If is the perimeter of a right angle triangle with integral length sides, {a, b, c}, there are exactly three solutions for

For which value of , is the number of solutions maximised? If there are multiple values print smallest.

Input Format

First line contains that denotes the number of test cases. This is followed by lines, each containing an integer, .

Constraints

Output Format

Print the required answer for each test case.

Sample Input

2
12
80

Sample Output

12
60