Minimum Cost to Connect Sticks

You are provided with an array, ARR, of N positive integers. Each integer represents the length of a stick. The task is to connect all sticks into one by paying a cost to join two sticks at a time. If you join two sticks with lengths X and Y, the cost is X + Y, and the resulting stick has a length of (X + Y). Determine the minimum cost to connect all the sticks into a single stick.

Input:

- The first line contains an integer T, representing the number of test cases.
- For each test case:
    * The first line contains an integer N, denoting the number of sticks.
    * The second line contains N space-separated integers, representing the length of each stick.

Output:

For each test case, output the minimum cost to connect all the sticks into one. Each result should be printed on a new line.

Example:

Input:

T = 1
N = 4
ARR = [2, 4, 3, 6]

Output:

29

Explanation:

We first join sticks of lengths 2 and 3, the cost is 5. Resulting sticks are [5, 4, 6].
Next, join sticks of lengths 5 and 4, the cost is 9. Resulting sticks are [9, 6].
Finally, join sticks of lengths 9 and 6, the cost is 15. The total cost is 5 + 9 + 15 = 29.

Constraints:

• 1 ≤ T ≤ 10
• 1 ≤ N ≤ 104
• 1 ≤ Val ≤ 5*103

Where:
- T is the number of test cases.
- N is the number of sticks.
- Val is the length of each stick.

Time Limit: 1 sec