AT_arc229_c [ARC229C] Sum of Average 2

You are given a length- $ N $ sequence of positive integers $ A=(A_1,A_2,\ldots,A_N) $ . Find the minimum possible value of $ \displaystyle \sum_{i=1}^{N-1}\left\lfloor\frac{A_i+A_{i+1}}2 \right\rfloor $ after rearranging $ A $ in any order. You are given $ T $ test cases; solve each of them.

The input is given from Standard Input in the following format: > $ T $ $ \text{case}_1 $ $ \text{case}_2 $ $ \vdots $ $ \text{case}_T $ Each test case is given in the following format: > $ N $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $

Output the answers for the test cases in order, separated by newlines.

### Sample Explanation 1 Consider the first test case. For example, rearranging $ A $ as $ (3,2,1,4) $ gives $ \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 $ . No matter how $ A $ is rearranged, the value of $ \displaystyle \sum_{i=1}^{N-1}\left\lfloor\frac{A_i+A_{i+1}}2 \right\rfloor $ is at least $ 5 $ , so the answer is $ 5 $ . ### Constraints - $ 1\le T\le 10^5 $ - $ 2\le N\le 2\times 10^5 $ - $ 1\le A_i\le 10^9 $ - The sum of $ N $ over all test cases is at most $ 2\times 10^5 $ . - All input values are integers.