Smallest Sum Combination

You are given an array of positive integers. Your task is to repeatedly perform the following operation until only one element remains:

Find the two smallest elements in the array, sum them, remove them from the array, and insert their sum back into the array.

Formally, if the array is \(a_1, a_2, \ldots, a_n\) (with \(n \ge 2\)) and sorted in non-decreasing order, then at each iteration, compute \(s = a_1 + a_2\) and update the array by removing \(a_1\) and \(a_2\) and appending \(s\). This process is repeated until only one element remains. Output this final element, which is the smallest possible sum obtainable via this process.

Example: For the array [4, 1, 3], the process is as follows:

• Sort: [1, 3, 4]
• Combine 1 and 3: 1 + 3 = 4, array becomes [4, 4]
• Combine 4 and 4: 4 + 4 = 8, array becomes [8]

The final output is 8.

inputFormat

The input begins with an integer T denoting the number of test cases. For each test case, the first line contains an integer N representing the number of elements in the array. The following line contains N positive integers separated by spaces.

Example:

2
3
4 1 3
4
1 2 3 4

outputFormat

For each test case, output a single line containing the smallest possible sum obtained by repeatedly combining the two smallest numbers in the array.

Example:

8
10

## sample

1
3
4 1 3

8

</p>