e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more

Elegant Permuted Sum

You will be given n integers {a1, a2, …, an}. Find a permutation of these 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 = |25| + |51| + |14| = 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.

Time limit 1 second
Memory limit 128 MiB
Input example #1
3
4 4 2 1 5
4 1 1 1 1
2 10 1
Output example #1
Case 1: 10
Case 2: 0
Case 3: 9