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⁶

1 ≤ A[i] ≤ 10⁶

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.