题目：满足和为 N 的勾股三元组的最大乘积

欧拉 第 9 题。 综合训练在讲解

勾股三元组（Pythagorean triplet）是满足以下条件的三个正整数 (a, b, c)：

• (a < b < c)
• $(a^2 + b^2 = c^2)$

例如： $(3^2 + 4^2 = 5^2)$，因此 (3, 4, 5) 是一个勾股三元组。

现在给定一个整数 (N)，请你判断是否存在某个勾股三元组 ((a, b, c)) 满足：

a + b + c = N

如果存在多个，请输出所有符合条件的三元组中 最大的乘积：

$a \times b \times c$

如果不存在任何满足条件的勾股三元组，则输出 -1。

输入格式

• 第一行包含一个整数 (T)，表示测试用例个数。
• 接下来 (T) 行，每行包含一个整数 (N)。

输出格式

对于每个测试用例，输出一个整数： 满足条件的勾股三元组中最大 (abc) 的值；若不存在则输出 -1。

数据范围

• $(1 \le T \le 3000)$
• $(1 \le N \le 3000)$

样例输入

2
12
4

样例输出

60
-1

样例解释

对于 (N = 12)： 存在三元组 (3, 4, 5)，并且：

$3 + 4 + 5 = 12,\quad 3^2 + 4^2 = 5^2,$$\quad 3 \times 4 \times 5 = 60$

因此输出 60。

对于 (N = 4)： 不存在正整数 (a < b < c) 满足和为 4 的勾股三元组，因此输出 -1。