You are given a rod of length n, and an array prices of size n which contains the prices of rods of lengths 1 to n. Find the maximum amount you can make if you cut up the rod optimally.

Example

n: 8
A: [1, 3, 4, 5, 7, 9, 10, 11]
Result: 12
Explanation: Rods of length 2 and 6 cost: 3 + 9

Testing

Input Format

The first line contains an integer ‘T’ denoting the number of test cases.
For each test case, the input has two lines:

• An integer ‘n’ denoting the length of the rod.
• n space-separated integers denoting the price of rods.

Output Format

For each test case, the output contains a line with one integer denoting the maximum amount possible.

Sample Input

3
8
1 3 4 5 7 9 10 11
6
3 5 8 10 14 15
7
2 8 11 14 15 19 21

Expected Output

12
18
27

Constraints

1 <= T <= 10
1 <= n <= 5000
1 <= pricesi <= 106
1 <= answer <= 109