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.
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.
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.
Example 1
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.