Rod Cutting Problem Statement

Given a rod of length 'N' units, you can cut the rod into different sizes, each with a specific cost associated. The task is to determine the maximum obtainable cost by cutting the rod and selling the resulting pieces.

Explanation:

Pieces must sum up to 'N', and you should consider 1-based indexing when looking at cost values.

Input:

The first line contains an integer 'T' denoting the number of test cases.
For each test case, the first line contains an integer 'N', the length of the rod.
The second line contains a vector 'A' of size 'N', where each index corresponds to a sub-length, and the element at each index indicates the cost of that sub-length.

Output:

For each test case, output a single integer denoting the maximum cost obtainable by selling the rod's pieces. Each result should be on a separate line.

Example:

If the rod length is 4 and the costs associated with lengths [1, 2, 3, 4] are [2, 5, 7, 8], the maximum cost by cutting optimally would be 10.

Constraints:

• 1 ≤ T ≤ 50
• 1 ≤ N ≤ 100
• 1 ≤ A[i] ≤ 100

The time limit for execution is 1 second.

Note:

No need to print the result; implementation of the function logic is required.