Water Supply

Time Limit: 3 Seconds    Memory Limit: 131072 KB

There are a lot of farm lands around Shahed University and supplying water for them is very important. Since they placed far from the city, water supplying facilities are very limited and each two adjacent farm lands must share their facilities equally. Between these lands, there are two adjacent lands A and B which encounter a problem with their shared water pumps recently. Each day, because of some unknown reasons, shared pumps behave differently. Some of the pumps may be deactivated and some of them may not pump the water as much as they must. For example, in the last day, there were only 3 active pumps which were pumped 20, 50 and 50 liters of water. Since these farmers are good people, they want to share the total amount of pumped water fairly. In other words, in each day, they want to assign each of these pumps to their lands in a way that the difference between amounts of pumped water to each land minimizes. For instance, last day, they assigned first and second pumps to the land A and the last pump to the land B. This decision resulted in the minimum difference of 20 liters.

Totally, there are 100 shared pumps between lands A and B, each of them is capable of pumping 500 liters of water. As mentioned before, each day there are n (0 <= n <= 100) available pumps, each of them can pump li liters of water (0 <= li <= 500 and 1 <= i <= n). Your task is to write a program to get the information of available pumps in each day and gives the minimum possible difference between amounts of pumped water to the lands A and B after the fair pump assignment. Please note that it is not possible to divide the amount of water supplied by a single pump and all of the available pumps must be used in the assignment.

Input

First line of the input contains an integer N which is number of days. For each day there is two lines. The first line contains integer n (number of available pumps) and the second line contains n space separated integers l1, ..., ln denoting the amount of water can be pumped by each of the available pumps.

Output

For each day, print a single line containing minimum possible difference between amounts of pumped water to the lands A and B after the fair assignment.

Sample Input

3
3
20 50 50
3
2 3 5
4
1 4 2 6

Sample Output

20
0
1
Submit