REDARR2  Reduce the array
Given an array of size n, you need to reduce the array. In one step, remove any two elements from the array and add their sum instead. Continue addition and removal until no further reduction possible. Output the minimum cost of reduction possible for the given array.
Input
First line contains a positive integer T representing number of testcases.
Next line contains a number n denoting the size of array.
Next line contains N space separated positive integers (A[i])
1 ≤ T ≤ 50
1 ≤ n ≤ 10^{6}
1 ≤ A[i] ≤ 10^{6}
Output
Output minimum cost of reduction.
Example
Input:
2
4
1 6 3 20
3
2 2 2
Output:
44
10
Explanation:
Example 1:
Remove {1,3} and insert 1+3=4, array becomes [4 6 20], cost=1+3=4
Next remove {4,6} and insert 4+6=10, array becomes [10 20], cost=4+6=10 and overall cost=4+10=14
Next remove {10,20} and insert 10+20=30, array becomes [30], cost=10+20=30 and overall cost=14+30=44
Array cannot be reduced further, hence reduction cost is 44. This sequence of reduciton also gives the minimum possible cost. You will see all other sequences give greater or equal cost.
Example 2:
Remove {2,2} and insert 2+2=4, array becomes [4 2 ], cost=2+2=4
Next remove {4,2} and insert 4+2=6, array becomes [6], cost=4+2=6 and overall cost=4+6=10
Array cannot be reduced further, hence reduction cost is 10.
hide comments
as_sami:
20201225 06:57:27
some hint...... <snip>


offamitkumar:
20200624 14:28:50
I'm not gonna spoil you but, whatever logic you use, choose long long instead of int. 

wesolyfoton:
20190924 22:16:35
@akshayjhamb2 Send me your code, then I can check it for you.


akshayjhamb2:
20190822 13:07:01
Kriti Joshi  could you please see my solution and tell me where am i making mistake? 
Added by:  Kriti Joshi 
Date:  20190722 
Time limit:  3s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 