You have been given an array consisting of n integers, (a1,a2,...an). You can perform the following operations:
Given the array find the maximum number of points you can score.
Input
The first line of the input contains T, the number of test cases.
The first line of each test case contains an integer n, denoting the size of the array.
Followed by n integers, (a1,a2,...an).
Output
For each test case print in a new line the maximum points that can be scored.
Constraints
1≤T≤10
1≤n≤105
0≤ai≤105
For the first test case,
Partitioning the array is not possible, hence the maximum achievable score is 0.
For the second test case,
Partitioning the array into {0, 2, 3} and {2, 3}.
Discarding the first partition,
Partitioning the second array into {2} and {3}.
Total score = 1 + 1 = 2