A. Adjacent Product Sum
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You have $$$n$$$ numbers $$$a_1, a_2, \ldots, a_n$$$. You want to arrange them in a circle so as to maximize the sum of products of pairs of adjacent numbers.

Formally, you want to find a permutation $$$b_1, b_2, \ldots, b_n$$$ of $$$a_1, a_2, \ldots, a_n$$$ such that $$$b_1b_2 + b_2b_3 + \ldots + b_{n-1}b_n + b_nb_1$$$ is maximal.

Find this maximum value.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$)  — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $$$n$$$ $$$(3 \le n \le 2\cdot 10^5)$$$  — the number of numbers.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^6 \le a_i \le 10^6$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

Output

For each test case, print a single integer  — the maximum possible value of the expression $$$b_1b_2 + b_2b_3 + \ldots + b_{n-1}b_n + b_nb_1$$$ over all permutations $$$b_1, b_2, \ldots, b_n$$$ of $$$a_1, a_2, \ldots, a_n$$$.

Example
Input
4
3
1 2 3
6
1 1 1 1 0 0
5
100000 100000 100000 100000 -100000
5
1 2 3 4 5
Output
11
3
10000000000
48
Note

In the first test case, there is only one way to arrange the numbers in a circle (not counting rotations and symmetries)  — $$$(1, 2, 3)$$$. The sum of products of pairs of adjacent numbers is $$$1\cdot 2 + 2\cdot 3 + 3\cdot 1 = 11$$$.

In the second test case, one of the optimal arrangements is $$$(1, 1, 1, 1, 0, 0)$$$. For it this sum is equal to $$$1 \cdot 1 + 1 \cdot 1 + 1 \cdot 1 + 1 \cdot 0 + 0 \cdot 0 + 0 \cdot 1 = 3$$$.

In the third test case, there is a unique (up to rotations and symmetries) way to arrange the numbers in a circle: $$$(100000, 100000, 100000, 100000, -100000)$$$, the answer is $$$100000^2 = 10^{10}$$$. Note that the answer may not fit into int32.

In the fourth test case, one of the optimal permutations is $$$(1, 2, 4, 5, 3)$$$, the answer for which is $$$1 \cdot 2 + 2 \cdot 4 + 4 \cdot 5 + 5 \cdot 3 + 3 \cdot 1 = 2 + 8 + 20 + 15 + 3 = 48$$$.