Minus Signs
-----------

The following mathematical expression appears in a Leutonian legal contract:

98 - 23 - 17 - 56

You know that Leutonians don't use parentheses.  Therefore, the 
expression could be interpreted in many ways to get different values.  
(This is one more reason that Leutonians have difficulty with mathematics.)  
For example,
((98 - 23) - 17) - 56 = 2
or
(98 - 23) - (17 - 56) = 114
or
98 - (23 - (17 - 56)) = 36
or
98 - ((23 - 17) - 56) = 148,
among other possibilities.

Since the expression represents the amount of money your neighbour
owes you, you want to find the interpretation that makes the expression's
value as large as possible.

Your goal is to write a programme that solves this problem in general:
for any sequence of integers separated by minus signs, what is the
maximum value that can be achieved by parenthesizing the expression?

Input
-----

The input will consist of multiple problem instances.  The first
line will contain a single integer n, representing the number of instances.

The input for each instance will appear on a line by itself.  That
line will contain an positive integer k <= 50 followed by k non-negative
integers separated by spaces.  You can assume that the integers in the
list will all be smaller than 1000.  For example, the expression
98 - 23 - 17 - 56
would have k = 4, and would be represented in the input by a line
4 98 23 17 56

Output
------

For each input instance, output (on a separate line) the maximum value 
that can be achieved by parenthesizing the expression represented
by the input.

Sample Input
------------

3
4 98 23 17 56
3 1 2 3
4 7 105 763 12

Sample Output
-------------

148
2
677