Adjacent Product Sum#12883

Adjacent Product Sum

1 second
256 megabytes
Hard

You have 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 (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 (3 \le n \le 2\cdot 10^5)  — the number of numbers.

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

It is guaranteed that the sum of 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 for all permutations b_1, b_2, \ldots, b_n of a_1, a_2, \ldots, a_n.

Examples

Example 1

Loading
Loading

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.