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=∣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.
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.
For each test case print the case number followed by the elegant permuted sum.