Maximum Possible Sum

You are given T test cases. For each test case, you are given an integer N representing the number of elements in an array and then N space‐separated integers. Your task is to split the array into two groups: non‐negative numbers and negative numbers.

Then, form pairs from each group:

• For any pair of non‐negative integers \(a\) and \(b\), their contribution is \(a+b\).
• For any pair of negative integers \(a\) and \(b\), their contribution is \(a \times b\).

If there is an unpaired element in any group, it is discarded. Compute and output the maximum possible sum for each test case.

inputFormat

The first line contains a single integer T denoting the number of test cases.

For each test case:

• The first line contains an integer N, the number of elements.
• The second line contains N space-separated integers.

outputFormat

For each test case, print a single line containing the maximum possible sum computed as described.

## sample

5
4
1 2 -3 -4
3
0 1 -2
2
5 -5
5
2 3 -1 -2 -3
4
-1 -2 -3 -4

15
1
0
7
14

</p>