Problem Statement:

Salwa is a brilliant student; she is just a six years old. She knew only one mathematical operation: addition (+). Yesterday she learned subtraction using minus operator (-). She went home and starts playing with it. She realized that when she subtract 3 numbers the answer depends on the order of executing the subtractions even when she didn't change the order of the 3 numbers themselves (subtraction is not an associative operation).

For example: 2 - ((5 - 1) - 8) = 6, while (2 - 5) - (1 - 8) = 4

She tried to find a way to maximize the answer of subtract sequence of numbers without changing their order. Of course, you will not let her alone with this mathematical task even when you have a competition to win! So please help her as a part of your competition.

Input Format:

First line contains K (1 ≤ K ≤ 100) number of test cases. Each line in the next K lines represents one test case, containing sequence of numbers that should be subtracted without changing their order. Each number is in range [1,999]. Each test case may contain from 1 to 150 numbers.

Output Format:

For each test case output one line containing one number represents the maximum answer of subtract test case sequence numbers without changing their order.

Sample Input:

2
2 5 1 8
6 2 1

Sample Output:

6
5