The Candyman Can |
The Candyman can. But can he really?
It's the first of October, the day Willy Wonka opens the doors to his famous Chocolate Factory
for the five lucky kids that hold one of the golden tickets: Charlie, Augustus, Mike, Veruca and
Violet. The tour guided by Willy Wonka begins, and after Augustus falls into the river of
chocolate and Violet turns into a blueberry (but don't worry, they are going to be safe and
healthy at the end), there are three of the children left.
What a shock! To calm down the remaining three children, Willy Wonka wants to give some candies to them. He has a couple of candies that are of different weight and wants to divide them evenly between the children, so that they don't get jealous at each other.
He wants to know how bad the fairest distribution is, i.e. what is the minimum difference in the candies weight, of the kid getting the candies of the most total weight and the kid getting the least. For example, assume that he gives the three children candies of weight a, b and c, respectively. The badness of this distribution is the difference between the maximum of a, b, c and the minimum of a, b, c. Unfortunately, Willy Wonka is not very good in mathematics, so he needs your help.
The first line of input contains a single integer (less than 130) indicating the number of testcases that follow. Each testcase consists of two lines. The first line contains a number n( 0 < n32), the number of candies to be distributed. The second line contains n numbers a1...an ( 0 < ai20 for all i = 1...n), the weight of the different candies.
4 3 2 2 2 2 3 4 6 13 9 7 7 1 7 8 3 3 3 3 3 3 5 5
Case 1: 0 Case 2: 4 Case 3: 2 Case 4: 1