Patrick is engaged in the WarFire game, where the objective is to assemble two teams from a pool of $N$ players represented by an array $A$. Each player possesses a specific power level, and the cumulative power level of a team is determined by the sum of individual player powers.

To ensure a closely contested match between the two teams, Patrick aims to minimize the gap in power levels between them.

Your task is to help Patrick and complete the challenge of finding the smallest possible gap between the total power levels of both teams.

Input Format:

Note: This is the input format that you must use to provide custom input (available above the Compile and Test button).

The first line contains $T$ denoting the number of test cases. $T$ also specifies the number of times you have to run the solve function on a different set of inputs.
For each test case:

• The first line contains the integer $N$.
• The second line contains the array $A$ of length $N$

Output Format:
For each test case, print the answer in a new line. 

Constraints:

$1 \leq T \leq 10 \\ 1 \leq N \leq 10^3 \\ 1 \leq A[i] \leq 10^3 \\ N*(Sum \ of \ elements) \leq 10^6$