Recently Jim decided to improve his pistol shooting skills. Today his coach offered him the following exercise. He placed cans in a row on a table. Cans are numbered from left to right from to . Jim has to knock down each can exactly once to finish the exercise. He is allowed to choose the order in which he will knock the cans down.
Jim knows that the durability of the can is . It means that if Jim has already knocked cans down and is now about to start shooting the one, he will need shots to knock it down. You can assume that if Jim starts shooting the can, he will be shooting it until he knocks it down.
Your task is to choose such an order of shooting so that the number of shots required to knock each of the given cans down exactly once is minimum possible.
Input Format
The first line contains the number of test cases, .
For each test case:
The first line contains one integer () — the number of cans.
The second line of the input contains the sequence (), where is the durability of the can.
Sample Input
1
3
20 10 20
Output Format
For each test case, print the minimum number of shots required to knock each of the given cans down exactly once.
Sample Output
43
You must be logged in to submit a solution.