Minimum Last Element

You are given an array of n integers. You need to perform a series of operations on the array until it becomes empty. In each operation, you select any two elements, remove them from the array, and add the absolute difference of these two elements back to the array. Your task is to determine the minimum possible value of the last remaining element after performing these operations optimally.

The key observation is based on the sum of all the elements and the maximum element, denoted as \(M\). Let \(S = \sum_{i=1}^{n} a_i\) and let the maximum element be \(M\). The answer is computed as follows:

• If \(S - M \ge M\), then the answer is \(S \mod 2\).
• Otherwise, the answer is \(M - (S - M)\).

This can be summarized by the formula:

[ \text{answer} = \begin{cases} S \mod 2, & \text{if } S - M \ge M, \ M - (S - M), & \text{otherwise.} \end{cases} ]

inputFormat

The first line contains an integer T representing the number of test cases. Each test case consists of two lines:

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

outputFormat

For each test case, output a single integer representing the minimum possible value of the last remaining element. Each answer should be printed on a new line.

## sample

3
3
3 7 11
4
1 1 1 1
5
2 2 5 8 13

1
0
0

</p>