A6998 | Game With Triangles: Season 2

Frontman 欢迎你来到这场生存游戏的最终回合。给定一个具有 $n$ 条边的正则多边形（$n \ge 3$），其顶点按顺时针顺序编号为 $1,2,\ldots,n$。每个顶点 $i$ 上被粉色士兵写有一个正整数 $a_i$。你需要基于这个正则多边形进行如下定义的游戏。

初始时你的得分为 $0$。你可以通过以下操作任意次来增加得分：

- 选择三个未被选择过的不同顶点 $i$、$j$、$k$，并绘制这三个顶点形成的三角形。
- 此时你的得分增加 $a_i \cdot a_j \cdot a_k$。
- 但若该三角形与之前绘制的任意三角形存在正面积的公共区域，则不能执行此操作。


左图为两次操作后的合法状态，右图状态不合法，因为两个三角形存在正面积的公共区域。
你的目标是最大化得分。请计算你在这场游戏中能获得的最大得分。

每个测试包含多个测试用例。第一行包含测试用例数量 $t$（$1 \le t \le 10^4$）。接下来是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$ —— 顶点数量（$3 \le n \le 400$）。

每个测试用例的第二行包含 $a_1,a_2,\ldots,a_n$ —— 顶点上的整数（$1 \le a_i \le 1000$）。

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

对于每个测试用例，在单独一行中输出可获得的最大得分。