#1563 BagsOfGold

47  1 s   128 MB  

Description

My partner and I have bags of gold, lined up in a row. The bags are different sizes. My partner has offered to split up the gold using the following system: we take turns, each time choosing one bag from either end of the line. She has even generously offered to let me go first -- hmmmmmmmm....
I need software to tell me the total amount of gold that I will get compared to how much my partner will get if I choose first. Of course we will assume that my partner and I are brilliant and always choose in the optimum way.

Input

The first line of the input gives a number of test cases, T (1 <= T <= 200).
The first line of each case gives a number of bags, N (1 <= N <= 50).
Next line gives N integers, the number of gold in each bag, separated by space. The number of gold in each bag is not greater than 100,000.

Output

For each test case, output the number how much more gold I will get than my partner.

Sample Input

Sample Output

2
2
7 2
3
2 7 3
5
-2