Debt

Mingyun goes by the nickname debtor. The Kim Woohyun lab gave it to him because he is slow to pay back what he borrows.

Mingyun has borrowed money $N$ times, and the $i$th loan is $A_i$. The lab collects its money in an unusual way.

When the lab orders Mingyun to settle $M$ debts, he picks any $M$ of the $N$ loans. If the picked amounts are $B_1, B_2, \dots, B_M$, he has to pay $\max(B_1, B_2, \dots, B_M) \times M$. The part he pays beyond the amounts he actually borrowed is the extra payment, so the extra payment is $\max(B_1, B_2, \dots, B_M) \times M - (B_1 + B_2 + \dots + B_M)$.

Suppose Mingyun borrowed $2$, $5$ and $3$ in three loans and the lab orders him to settle two debts. If he picks the first and the second loan, he pays $5 \times 2 = 10$ and the extra payment is $10 - (2 + 5) = 3$. If he picks the first and the third loan, he pays $3 \times 2 = 6$ and the extra payment is $6 - (2 + 3) = 1$.

Mingyun wants the extra payment to be as small as possible. Let $S(M)$ be the smallest extra payment he can reach when the lab orders him to settle $M$ debts.

For $N = 5$ with the loans $1, 5, 4, 3, 8$ in that order:

• $S(1) = 0$. Any single loan works.
• $S(2) = 1$. Pick $5$ and $4$, or pick $4$ and $3$.
• $S(3) = 3$. Pick $5, 4, 3$.
• $S(4) = 7$. Pick $5, 4, 3, 1$.
• $S(5) = 19$. Pick all five.

Given $N$ and $A_1, A_2, \dots, A_N$, compute $S(1) + S(2) + \dots + S(N)$.

The first line has the number of test cases $T$ ($1 \le T \le 10$).

Each of the next $T$ lines has the number of loans $N$ ($1 \le N \le 4000$) followed by the borrowed amounts $A_1, A_2, \dots, A_N$ ($1 \le A_i \le 10000$), separated by spaces.

For each test case, print $S(1) + S(2) + \dots + S(N)$ on its own line.

The answer and the intermediate values can exceed the 32-bit integer range, so use a 64-bit integer type.