## REDARR2 - Reduce the array

no tags

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 ≤ 106

1 ≤ A[i] ≤ 106

### Output

Output minimum cost of reduction.

### Example

`Input:241 6 3 2032 2 2`
`Output:4410`
`Explanation:Example 1:Remove {1,3} and insert 1+3=4, array becomes [4 6 20], cost=1+3=4Next remove {4,6} and insert 4+6=10, array becomes [10 20], cost=4+6=10 and overall cost=4+10=14Next remove {10,20} and insert 10+20=30, array becomes , cost=10+20=30 and overall cost=14+30=44Array 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=4Next remove {4,2} and insert 4+2=6, array becomes , cost=4+2=6 and overall cost=4+6=10Array cannot be reduced further, hence reduction cost is 10.` as_sami: 2020-12-25 06:57:27 some hint...... [NG]: Nobody asked you for one. Last edit: 2020-12-25 16:45:01 offamitkumar: 2020-06-24 14:28:50 I'm not gonna spoil you but, whatever logic you use, choose long long instead of int. wesolyfoton: 2019-09-24 22:16:35 @akshayjhamb2 Send me your code, then I can check it for you. akshayjhamb2: 2019-08-22 13:07:01 Kriti Joshi - could you please see my solution and tell me where am i making mistake?