Description

This problem is a programming version of Problem 39 from projecteuler.net
If p is the perimeter of a right angle triangle with integral length sides, {a, b, c}, there are exactly three solutions for p = 120 {20,48,52},{24,45,51},{30,40,50}
For which value of p ≤ N, is the number of solutions maximised? If there are multiple values print smallest.
Input Format
First line contains T that denotes the number of test cases. This is followed by T lines, each containing an integer, N.
Output Format
Print the required answer for each test case.
Constraints
1 ≤ T ≤ 105 12 ≤ N ≤ 5 × 106
Sample Input

Sample Output