A121005.小枫的三角形游戏

小枫、小午和小安正在玩一个多边形上的游戏。

小枫在纸上画了一个正 $n$ 边形，顶点按顺时针依次编号为 $1, 2, \dots, n$。
在每个顶点 $i$ 上，小午写了一个正整数 $a_i$。

游戏规则如下：

• 初始时，小安的得分为 $0$。
• 小安可以重复执行以下操作任意多次：
  1. 选择三个之前从未选过的顶点 $i, j, k$，画出以这三个点为顶点的三角形。
  2. 得分增加 $a_i \cdot a_j \cdot a_k$。
  3. 但不能画出与之前任何已画三角形有正面积重叠的三角形（即两个三角形的内部不能有公共部分）。

小安希望最大化最终得分，你能帮小安算出最大可能得分吗？

每个测试点包含多个测试用例。
第一行一个整数 $t$——测试用例的数量。

每个测试用例包含两行：

• 第一行一个整数 $n$——多边形的顶点数。
• 第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$——每个顶点上的数值。

数据保证所有测试用例的 $n^3$ 之和不超过 $400^3$。

对于每个测试用例，输出一行一个整数，表示小安能获得的最大得分。

数据范围

对于 $100\%$ 的测试数据，满足：$1 \le t \le 10^4$，$3 \le n \le 400$，$1 \le a_i \le 1000$ 。