AT_arc229_c [ARC229C] Sum of Average 2

長さ $ N $ の正整数列 $ A=(A_1,A_2,\ldots,A_N) $ が与えられます。 $ A $ を好きな順序に並べ替えた後の $ \displaystyle \sum_{i=1}^{N-1}\left\lfloor\frac{A_i+A_{i+1}}2 \right\rfloor $ としてあり得る最小値を求めてください。 $ T $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \text{case}_1 $ $ \text{case}_2 $ $ \vdots $ $ \text{case}_T $ 各テストケースは以下の形式で与えられる。 > $ N $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $

各テストケースに対する答えを順に改行区切りで出力せよ。

### Sample Explanation 1 $ 1 $ 番目のテストケースについて考えます。 たとえば $ A=(3,2,1,4) $ に並べ替えることで $ \displaystyle \sum_{i=1}^{N-1}\left\lfloor\frac{A_i+A_{i+1}}2 \right\rfloor=\left\lfloor\frac52\right\rfloor+\left\lfloor\frac32\right\rfloor+\left\lfloor\frac52\right\rfloor=5 $ となります。 どのように並べ替えても $ \displaystyle \sum_{i=1}^{N-1}\left\lfloor\frac{A_i+A_{i+1}}2 \right\rfloor $ の値は $ 5 $ 以上となるため、答えは $ 5 $ になります。 ### Constraints - $ 1\le T\le 10^5 $ - $ 2\le N\le 2\times 10^5 $ - $ 1\le A_i\le 10^9 $ - 全てのテストケースにおける $ N $ の総和は $ 2\times 10^5 $ 以下 - 入力される値は全て整数