Minimum Cost to Reduce Array Problem Statement

You are given an array ARR containing N positive integers. Your task is to reduce the size of this array to 1 by repetitively merging adjacent elements. Each time you merge two adjacent elements, the cost incurred will be equal to their sum. Find the minimum total cost to reduce the array to a single element by performing these operations.

Explanation:

In a single merge operation, adjacent elements are removed, and their sum is inserted in their place, reducing the array size by one. Only N-1 merge operations are needed for an array of size N.

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, the size of the array. The second line contains N space-separated integers representing the array elements.

Output:

For each test case, output a single integer representing the minimum cost of merging the entire array.

Example:

Input:

2
4
1 2 3 4
3
10 20 30

Output:

19
60

Constraints:

• 1 ≤ T ≤ 50
• 1 ≤ N ≤ 100
• 1 ≤ ARR[i] ≤ 10^6
• Time Limit: 1 sec

Note:

The aim is to minimize the total cost of merging by strategically choosing which pairs to merge at each step.