You are given an array A of size (N≥2).

We define
�
(
�

)

∑

�

1
�
−
1
(
�
�
+
�
�
+
1
)
f(A)=∑
i=1
N−1
​
(A
i
​
+A
i+1
​
).

Find the maximum value of
�
(
�
)
f(A) you can obtain by rearranging the elements of
�
A in any arbitrary order.

Input Format
The first line of input will contain a single integer
�
T, denoting the number of test cases.
Each test case consists of multiple lines of input.
The first line of each test case contains one integer,
�
N, the size of the array.
The next line contains
�
N space-separated integers,
�
1
,
�
2
,
…
,
�
�
A
1
​
,A
2
​
,…,A
N
​
.
Output Format
For each test case, output on a new line, the maximum value of
�
(
�
)
f(A) you can obtain by rearranging the elements of
�
A in any arbitrary order.

Constraints
1
≤
�
≤
2
⋅
1
0
4
1≤T≤2⋅10
4

2
≤
�
≤
1
0
5
2≤N≤10
5

1
≤
�
�
≤
1
0
4
1≤A
i
​
≤10
4

The sum of
�
N over all test cases does not exceed
1
0
5
10
5
.
Sample 1:
Input
Output
2
2
3 6
5
2 2 1 2 2
9
15
Explanation:
The first sample has
2
2 valid arrays :
[
3
,
6
]
[3,6] and
[
6
,
3
]
[6,3], both have
�
(
�

)

9
f(A)=9.

For the second sample, one optimal array is
[
1
,
2
,
2
,
2
,
2
]
[1,2,2,2,2], which has
�
(
�

)

f(A)=
(
1
+
2
)
+
(
2
+
2
)
+
(
2
+
2
)
+
(
2
+
2

)

15
(1+2)+(2+2)+(2+2)+(2+2)=15.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        vector<int> arr(n);
        for (int i = 0; i < n; i++) {
            cin >> arr[i];
        }

        sort(arr.begin(), arr.end(), greater<int>());

        long long sum = 0;
        for (int i = 0; i < n - 1; i++) {
            sum += arr[i] + arr[i + 1];
        }

        cout << sum << endl;
    }

    return 0;
}