A maximum sum subsequence of an array is subsequence whose sum is maximum with the condition that the subsequence is sorted.

Given an array, find the sum of the maximum sum subsequence of that array.

Example

arr: [101, 4, 98, 103]
answer: 205
Explanation: 4+98+103

arr: [101, 4, 95, 103]
answer: 204
Explanation: 101+103

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 size of the array.
• n space-separated integers denoting the array.

Output Format

For each test case, the output contains a line with one integer denoting the sum of the max sum subsequence.

Sample Input

3
4
101 4 98 103
4
101 4 95 103
1
42

Expected Output

205
204
42

Constraints

1 <= T <= 100
1 <= n <= 100
1 <= arri <= 1000