Maximum Increasing Subsequence Score

You are given an array of integers, and your task is to compute the maximum possible sum (score) of any increasing subsequence that can be formed from the array. An increasing subsequence is defined as a sequence of elements from the array (not necessarily contiguous) where each subsequent element is strictly larger than the previous one.

Let \( dp[i] \) denote the maximum score for an increasing subsequence ending at index \( i \). The recurrence relation is given by:

[ dp[i] = a_i + \max_{j < i \text{ and } a_j < a_i} { dp[j] } ]

If there is no such \( j \), then \( dp[i] = a_i \). Your job is to calculate \( \max_i dp[i] \) for the given array.

The input will consist of multiple test cases. For each test case, first you are given the number of elements \( n \) followed by \( n \) integers representing the sequence. Output one number for each test case on a separate line.

inputFormat

The first line of the input contains an integer \( T \) representing the number of test cases. For each test case, the input is structured as follows:

• The first line contains a single integer \( n \), the number of elements in the sequence.
• The second line contains \( n \) space-separated integers, representing the array.

Example:

2
5
3 -1 4 -2 5
4
7 7 7 7

outputFormat

For each test case, output a single line containing one integer, the maximum sum that can be obtained by an increasing subsequence.

Example:

12
7

## sample

2
5
3 -1 4 -2 5
4
7 7 7 7

12
7

</p>