403177: GYM101061 F Fairness

Dwik and his brother Samir both received scholarships from a famous university in India. Their father, Besher, wants to send some money with each of them.

Besher has n coins, the i^th coin has a value of a_i. He will distribute these coins between his two sons in n steps. In the i^th step, he chooses whether to give the i^th coin to Dwik or to Samir.

Let x_i be the absolute difference between the sum of Dwik's and Samir's coins after the i^th step. The unfairness factor of a distribution is max({x₁, x₂, ..., x_n}). Besher wants to minimize the unfairness factor, can you help him?

The first line of the input consists of a single integer t, the number of test cases. Each test case consists of 2 lines:

The first line contains an integer n (1 ≤ n ≤ 100).

The second line contains n integers a₁, a₂, ..., a_n (1 ≤ a_i ≤ 100).

Print t lines, i^th line containing a single integer, the answer to the i^th test case.

2
5
1 2 1 4 3
7
4 5 6 1 1 3 4

2
5

In the first sample test, besher has 5 coins (1, 2, 1, 4, 3), he can distribute them in the following way:

Step 1: Give the first coin to dwik , d = 1, s = 0 x₁ = |1 - 0| = 1

Step 2: Give the second coin to samir, d = 1, s = 2 x₂ = |1 - 2| = 1

Step 3: Give the third coin to samir, d = 1, s = 3 x₃ = |1 - 3| = 2

Step 4: Give the fourth coin to dwik, d = 5, s = 3 x₄ = |5 - 3| = 2

Step 5: Give the fifth coin to samir, d = 5, s = 6 x₅ = |5 - 6| = 1

max({x₁, x₂, x₃, x₄, x₅}) = 2