Joining two ropes costs the sum of their lengths. Find the minimum total cost to join every rope into one rope.

Input

The first line contains T. Each test case contains N followed by a line of N rope lengths.

• 1 <= T <= 100
• 1 <= N <= 10^6

Output

For each test case, print the minimum total cost.

Example

Input

2
4
4 3 2 6
3
1 2 3

Output

29
9