Maximum Profit Problem Statement

Ninja has a rod of length 'N' units and wants to earn the maximum money by cutting and selling the rod into pieces. Each possible cut size has a specific cost associated with it. Determine the maximum money he can earn by cutting the rod optimally and selling its pieces.

Input:

The first line of input contains an integer 'T' denoting the number of test cases.

The next 2 * T lines represent the 'T' test cases.

The first line of each test case contains an integer 'N' denoting the length of the rod.

The second line of each test case contains a vector 'A' of size 'N' representing the cost of different lengths, where each index is the sub-length, and the element at that index is the cost for that sub-length.

Output:

For each test case, print a single integer that is the maximum profit obtained by selling the pieces.

The output of each test case will be printed in a separate line.

Example:

Input:

T = 1
N = 8
A = [1, 5, 8, 9, 10, 17, 17, 20]

Output:

22

Explanation:

The best way to cut the rod of length 8 is into pieces of length 2 and 6, which provides a total profit of 5 + 17 = 22.

Constraints:

• 1 <= T <= 50
• 1 <= N <= 100
• 1 <= A[i] <= 100
• Consider 1-based indexing.

Note:

You do not need to print anything; it has already been taken care of. Just implement the function and return the answer.