大吉有一个包含n个整数的数组，她想要重新排列数组的元素，使得相邻两个元素的加和之和最大。即最大化：
S=(a1+a2)+(a2+a3)+...+(an−1+an)。
你的任务就是帮助小苯找到最大的s值。

每个测试文件均包含多组测试数据。第一行输入一个整数T(1<=T=10)代表数据组数，每组测试数据描述如下：
第一行包含一个整数n$(2\leqq n\leqq 200)$，表示数组的长度。
第二行n个整数表示数组的每个值 ai (1≦ai≦10e5)。

对于每组测试数据： 在单独的一行输出一个整数，表示最大的s值。

对于第一组测试数据，我们可以重排为:{2,4,3,1}时最优，此时s=(2+4)+(4+3)+(3+1)=17，最大。