你有 $n$ 个数 $a_1, a_2, \dots, a_n$。你希望将它们排列成一个圆圈，以最大化相邻数字乘积之和。

形式化地，你需要找到 $a_1, a_2, \dots, a_n$ 的一个排列 $b_1, b_2, \dots, b_n$，使得 $b_1b_2 + b_2b_3 + \dots + b_{n-1}b_n + b_nb_1$ 最大。

求这个最大值。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 10^4$)，表示测试用例的数量。接下来是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$ ($3 \le n \le 2 \cdot 10^5$)，表示数字的个数。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($-10^6 \le a_i \le 10^6$)。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出一个整数，表示在 $a_1, a_2, \dots, a_n$ 的所有排列 $b_1, b_2, \dots, b_n$ 中，表达式 $b_1b_2 + b_2b_3 + \dots + b_{n-1}b_n + b_nb_1$ 的最大可能值。

样例

样例输入 1

4
3
1 2 3
6
1 1 1 1 0 0
5
100000 100000 100000 100000 -100000
5
1 2 3 4 5

样例输出 1

11
3
10000000000
48

说明

在第一个测试用例中，将数字排列成圆圈只有一种方式（不计旋转和对称）—— $(1, 2, 3)$。相邻数字乘积之和为 $1 \cdot 2 + 2 \cdot 3 + 3 \cdot 1 = 11$。

在第二个测试用例中，最优排列之一是 $(1, 1, 1, 1, 0, 0)$。对于该排列，和为 $1 \cdot 1 + 1 \cdot 1 + 1 \cdot 1 + 1 \cdot 0 + 0 \cdot 0 + 0 \cdot 1 = 3$。

在第三个测试用例中，将数字排列成圆圈只有唯一一种方式（不计旋转和对称）：$(100000, 100000, 100000, 100000, -100000)$，答案为 $100000^2 = 10^{10}$。注意答案可能无法存入 int32。

在第四个测试用例中，最优排列之一是 $(1, 2, 4, 5, 3)$，其对应的答案为 $1 \cdot 2 + 2 \cdot 4 + 4 \cdot 5 + 5 \cdot 3 + 3 \cdot 1 = 2 + 8 + 20 + 15 + 3 = 48$。