Minimum Total Cost After Discount

You are given several test cases. In each test case, you have an array of item prices. Under a special discount promotion, when buying two items, you only have to pay the price of the cheaper item, and the more expensive one is free.

If there is an odd item out, you must pay its price in full.

Discount Rule: For every pair of items, the discount is applied to the more expensive item. This means that after sorting the prices in descending order, you pair the items and sum the price of the cheaper one in each pair. If there is an extra item (i.e. the number of items is odd), you add its price to the total cost.

Example:

• For the list [1, 3, 4, 2], after sorting: [4, 3, 2, 1], the pairs are (4, 3) and (2, 1). The total cost is 3 + 1 = 4.
• For the list [10, 20, 30, 40, 50, 60], after sorting: [60, 50, 40, 30, 20, 10], the pairs are (60, 50), (40, 30), and (20, 10). The total cost is 50 + 30 + 10 = 90.

Input Format: The first line contains an integer T, the number of test cases. For each test case, the first line contains an integer n (the number of items), followed by a line with n space-separated integers denoting the prices of the items.

Output Format: For each test case, output a single line containing an integer, the minimum total cost after applying the discount.

inputFormat

The input begins with an integer T, denoting the number of test cases. Each test case starts with an integer n, representing the number of items, followed by a line with n space-separated integers representing the prices.

outputFormat

For each test case, output a single integer — the minimum total cost after discount — on a new line.## sample

2
4
1 3 4 2
5
5 5 5 5 5

4
15