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. 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). For each test case, output a single integer — the minimum number of emeralds Steve must give away to make everyone friends. 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 grum