You will be given integers . Find a permutation of these 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 . The permutation yields the maximum summation. For this permutation . Of all the permutations, you won't get any summation whose value exceeds .
The first line is the number of test cases . Each case consists of a line that starts with followed by non-negative integers. None of the elements of the given permutation will exceed .
For each test case print the case number followed by the elegant permuted sum.