Maximum Score Calculation

You are given several test cases. For each test case, you are given an integer N followed by N integers. Your task is to calculate the maximum score that Alice can achieve using a specific operation.

The operation is defined as follows: sort the list of integers in ascending order. Then, pair the largest numbers by taking two elements at a time from the end. For each pair, add the smaller number of the two to the score. If there is an unpaired element (i.e. when the number of integers is odd), add the smallest integer (which is at the beginning of the sorted list) to the score.

Note: All arithmetic operations are to be performed with integer precision.

Example: For the test case with N = 3 and integers [1, 2, 3], after sorting we have [1, 2, 3]. Pairing the last two elements gives a pair (2, 3) where 2 is added. The unpaired integer is 1, leading to a total score of 3.

inputFormat

The first line of input contains a single integer T, representing the number of test cases.

For each test case, the first line contains an integer N, the number of integers. The following line contains N space-separated integers.

Input Format Example:

2
3
1 2 3
4
4 5 6 7

outputFormat

For each test case, output the maximum score on a new line.

Output Format Example:

3
10

## sample

2
3
1 2 3
4
4 5 6 7

3
10

</p>