Background

Special for algorithm lovers, ^_^

Description

给定 $n$ 个非负整数 $x_1, x_2, \dots, x_n$。

对于任意 $n$ 个节点的无向连通图 $G$，将其节点标号为 $1$ 至 $n$，其分数定义为：

$$\text{score}(G) = \sum_{i=1}^n \sum_{j=i+1}^n \text{dist}_G(i, j) \cdot x_i \cdot x_j $$

其中 $\text{dist}_G(i, j)$ 表示图 $G$ 上 $i$ 到 $j$ 的最短路径长度。

你的任务是：输出所有 $n$ 个节点的无向连通图中分数的最大值。

Format

Input

多组测试数据。

第一行一个整数 $t$ ($1 \le t \le T_{\max}$)，表示测试数据组数。

每组测试数据：

• 第一行一个整数 $n$ ($1 \le n \le N_{\max}$)；
• 第二行 $n$ 个整数 $x_1, x_2, \dots, x_n$，$0 \le x_i \le V_{\max}$。

保证所有测试数据的 $n$ 之和不超过 $N_{\max}$。

Output

对于每组测试数据，输出一个整数，表示所有无向连通图中分数的最大值。

Samples

3
2
1 2
4
1 0 1 1
7
1 2 3 4 5 6 7

2
6
1044

样例解释：

• 第一组：唯一的合法方案 $G = {(1,2)}$。
• 第二组：最优方案为 $G = {(1,2), (2,3), (2,4)}$。