war-point

Now it's time for actual battle between Ram and Ravana.  Battle field is given in the form of an array of integers.  But Ram has no idea about the field, so he asked Angad to help him out.  Now, Angad has decided a strategy to divide the field into exactly two parts such that the difference between the powers for the two parts is as minimum as possible. The  Power of a part is defined as the sum of the elements in that part.

Input:

First line contains T, denoting the number of test cases.

Each test case contains 2 lines:

First line contains an integer N denoting the size of  the array

Second line consists of N space separated integers.

Output:

Output the required answer in new line. 

Constraints:

0 <  T ≤ 20

1 < N ≤ 100000

-10^8 ≤ A[i] ≤ 10^8

Note:

Both parts has to be contiguous.

Large input/output files,  use scanf() , printf() for fast I/OSAMPLE INPUT
2
2 
1 2 
3
1 2 3

SAMPLE OUTPUT
1
0

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions: