For the given array [ 1, 3, 1, 2, 4 ].
The optimal way will be:
Mix the last two elements. The array will be [1, 3, 1, 6 ], and the smoke will be 8.
Mix the first two elements. The array will be [4, 1, 6 ], and the smoke will be 11.
Mix the last two elements. The array will be [4, 7], and the smoke will be 17.
Mix the remaining two elements. The array will be [11], and the smoke will be 45.
So, the output will be 45.
The first line contains a single integer ‘T’ denoting the number of test cases to be run. Then the test cases follow.
The first line of each test case contains a single integer ‘N’, representing the number of potions.
The second line of each test case contains ‘N’ space-separated integers representing the color value of the potions.
For each test case, print a single-digit integer representing the minimum amount of smoke generated.
Output for each test case will be printed in a separate line.
You are not required to print anything, it has already been taken care of. Just implement the function.
1 <= T <= 10
1 <= N <= 100
0 <= X <= 99
Where ‘X’ is the color value of a potion.
It is guaranteed that the sum of ‘N’ over all test cases doesn’t exceed 100.
Time Limit: 1 sec.