11158 - Elegant Permuted Sum

E Next Generation Contest 3 Time Limit: 2 seconds Elegant Permuted Sum

給 n 個整數  <A₁A₂A₃...A_n> 找到一種 n 個數字的排列方式，其中相鄰兩數字的差取絕對值加總後要最大。

假設 n = 4，這四個整數為 <4 2 1 5>，而排列 <2 5 1 4> 為最大的總和，
其總和為 sum = abs(2-5) + abs(5-1) + abs(1-4) = 3+4+3 = 10

所有的排列共有 24 種，並不會有其他的總和大於 10。

因此稱這個值為 elegant permuted sum。

Input

每組第一行會有一個整數 T (T < 100) 表示測資組數。

每組測資第一個整數 n (1 < n < 51) 表示接下來會有 n 個非負整數，且每個數字不超過 1000。

Output

對於每組測資，輸出測資組編號以及  elegant permuted summation。

Sample Input	Output for Sample Input
3 4 4 2 1 5 4 1 1 1 1 2 10 1	Case 1: 10 Case 2: 0 Case 3: 9

Problem Setter: Sohel Hafiz
Special Thanks: Jane Alam Jan