129. Subtraction

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

 Added by: samiemad Added at: 2014-02-26 01:15:09 UTC Time Limit: 3 seconds Partial score: No Source: ACM Syrian Collegiate Programming Contest 2013