Given a number of ropes say ‘N’ and an array of integers of size ‘N’ containing the length of ropes. Your task is to connect the ropes into one. The cost to connect two ropes is equal to the sum of their lengths. Find the minimum cost for connecting all the ropes.
The first line of input contains a single integer T, representing the number of test cases or queries to be run.
Then the T test cases follow.
The first line of each test case contains the number of ropes.
The second line of each test case contains space-separated integers containing the length of ropes.
For each test case, print the minimum cost to connect all the ropes. Each value is separated by a single space.
The output of each test case is printed in a separate line.
Note :
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 10
1 <= N <= 10^4
1 <= length[i] <= 10^4
Where 'length[i]' is the length of the 'i-th' rope.
Time Limit: 1 sec
Sample Input 1:
2
4
4 3 2 6
3
1 1 8
Sample Output 1:
29
12
Explanation for Sample Input 1:
For test case 1
Optimal way to connect the ropes is:
Connecting 3 and 2 costs 5.
Ropes left = [4,5,6]
Connecting 4 and 5 costs 9.
Ropes left = [9,6]
Connecting 9 and 6 costs 15.
One rope of length 15 is made.
Total cost for all the connections = 5 + 9 + 15 = 29.
Sample Input 2:
2
3
5 3 8
1
3
Sample Output 2:
24
0