B. Villagers
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Steve lives in a village with $$$n$$$ other villagers. Unfortunately, due to disputes over the distribution of emeralds, none of those villagers are friends with any other villager. Furthermore, villager $$$i$$$ initially has a grumpiness of $$$g_i$$$.

Steve can perform the following operation any number of times:

  • Select two villagers $$$i$$$ and $$$j$$$ and give them $$$\text{max}(g_i, g_j)$$$ emeralds to share. Both of their grumpinesses decrease by $$$\text{min}(g_i, g_j)$$$, and they become friends with each other if they weren't already.

Steve wishes to make every villager friends with every other villager (possibly through some intermediate friendships); that is, from any villager, you can follow a path of friendships to reach any other villager. Since he does not want to inflate the village economy too much, calculate the minimum number of emeralds he must give away to accomplish this.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the number of villagers.

The second line of each test case contains $$$n$$$ integers $$$g_1, g_2,\ldots, g_n$$$ ($$$1 \le g_i \le 10^9$$$) — the initial grumpiness of each villager.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output a single integer — the minimum number of emeralds Steve must give away to make everyone friends.

Example
Input
4
2
1 2
4
2 1 5 2
5
1000000000 1000000000 1000000000 1000000000 1000000000
6
3 1 4 1 5 9
Output
2
7
3000000000
14
Note

In the first test case, the only valid operation is $$$i = 1$$$, $$$j = 2$$$. Steve gives them $$$\text{max}(1, 2) = 2$$$ emeralds, and they become friends.

In the second test case, one optimal sequence of operations is as follows:

  • Steve chooses $$$i = 1$$$, $$$j = 3$$$. He gives the villagers $$$\text{max}(2, 5) = 5$$$ emeralds, and their grumpiness decreases by $$$\text{min}(2, 5) = 2$$$. Now everyone's grumpiness is $$$[0, 1, 3, 2]$$$;
  • Steve chooses $$$i = 2$$$, $$$j = 4$$$. He gives the villagers $$$\text{max}(1, 2) = 2$$$ emeralds, and their grumpiness decreases by $$$\text{min}(1, 2) = 1$$$. Now everyone's grumpiness is $$$[0, 0, 3, 1]$$$;
  • Steve chooses $$$i = 1$$$, $$$j = 2$$$. He gives the villagers $$$\text{max}(0, 0) = 0$$$ emeralds, and their grumpiness decreases by $$$\text{min}(0, 0) = 0$$$. Now everyone's grumpiness is $$$[0, 0, 3, 1]$$$.

After this, the pairs of villagers $$$(1, 3)$$$, $$$(2, 4)$$$ and $$$(1, 2)$$$ are directly friends, and every other pair of villagers is connected by a chain of mutual friendships. It can be shown that Steve cannot spend fewer than $$$7$$$ emeralds to accomplish this.