畢業的季節要到了. 為了給他女朋友一個畢業禮物, 大衛霍夫曼決定打造一個金鍊子. 他收集了很多的金條並且打算送到打鐵店把他們通通連成一條. 而打鐵店很有個性的每次只能連接兩個金條, 而連起來的價錢就是兩個金條長度相加, ex:長度2和長度3的連接起來的價錢為5 大衛是個窮苦的學生, 所以他希望能夠讓組合的價錢越低越好, 身為好朋友的你, 能不能幫他算出最低的組合價錢呢？！
第一行輸入一個整數T(<=20), 表示有幾組測試資料. 每組測試資料描述了大衛要買得鍊子資訊. 接下來每組會先輸入一個N(1<=N<=40000), 表示大衛要買得鍊子數量. 接下來N個數字L1, L2, ..., LN, 描述了這N個鍊子的長度.
對每組測試資料, 印出一行大衛要花的最少價錢