You are given an array \(A\) of length \(N\). There are two empty arrays, \(B\) and \(C\). You have to put every element of \(A\) into either \(B\) or \(C\).

The score of an array is defined as the square of the sum of all of its elements. Find the minimum possible absolute difference between the score of \(B\) and \(C\).

Input Format:

The first line of input contains a single integer \(T\), denoting the number of test cases.
The first line of each test case contains a single integer \(N\), denoting the length of the array \(A\).
The second line of each test case contains \(N\) integers, denoting the elements of array \(A\).

Output Format:

For each test case, print the minimum possible absolute difference between the score of \(B\) and the score of \(C\).

Constraints:

\(1 <= T <= 10\)

\(1 <= N <= 20\)

\(1 <= A[i] <= 10^8\)