# Greedy

# Elegant permuted sum

You will be given **n** integers {`a`

, _{1}`a`

, …, _{2}`a`

}. Find a permutation of these _{n}**n** integers so that summation of the absolute differences between adjacent elements is maximized. We will call this value the elegant permuted sum.

Consider the sequence {**4**, **2**, **1**, **5**}. The permutation {**2**, **5**, **1**, **4**} yields the maximum summation. For this permutation sum = |**2** – **5**| + |**5** – **1**| + |**1** – **4**| = **3** + **4** + **3** = **10**. Of all the **24** permutations, you won't get any summation whose value exceeds **10**.

#### Input

The first line is the number of test cases **t** (**t** < **100**). Each case consists of a line that starts with **n** (**1** < **n** < **51**) followed by **n** non-negative integers. None of the elements of the given permutation will exceed **1000**.

#### Output

For each test case print the case number followed by the elegant permuted sum.

3 4 4 2 1 5 4 1 1 1 1 2 10 1

Case 1: 10 Case 2: 0 Case 3: 9