The Candyman Can

“Who can take a sunrise
Sprinkle it with dew
Cover it in chocolate and a miracle or two
The Candy Man
The Candy Man can
The Candy Man can 'cause he mixes it with love
And makes the world taste good”

(taken from the movie “Willy Wonka and the Chocolate Factory”, 1971)

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 among 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 between 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.

Input Specification

The first line of the input contains a single integer (less than 130) indicating the number of test cases that follow. Each test case consists of two lines. The first line contains a number n (0 < n ≤ 32), the number of candies to be distributed. The second line contains n numbers a₁, …, a_n (0 < a_i ≤ 20 for all i = 1, …, n), the weights of the different candies.

Output Specification

For each test case, output a single line which contains the case number (as shown in the sample output) and then the smallest badness that can be achieved when distributing all candies to the children. There is only a single space between the colon and the smallest badness.

Sample Input

1. 4
2. 3
3. 2 2 2
4. 2
5. 3 4
6. 6
7. 13 9 7 7 1 7
8. 8
9. 3 3 3 3 3 3 5 5

download as text file

Output for Sample Input

1. Case 1: 0
2. Case 2: 4
3. Case 3: 2
4. Case 4: 1

download as text file