Shopaholic

Lindsay is a shopaholic. Whenever a store runs a promotion where you buy three items and pay for only two, she cannot resist buying every item in the store. You have given up on curing her, but you still try to limit the damage to her wallet.

In these promotions the free item is always the cheapest one among the items placed on the counter together: for every three items brought to the counter at the same time, the cheapest of those three is free. For example, if she brings seven items costing 400, 350, 300, 250, 200, 150, and 100 dollars all at once, she pays 1500 dollars, a discount of 250 dollars. By splitting the items across several trips to the counter she can do better. For instance, bringing 400, 300, and 250 together gives a discount of 250; bringing only the 150 item next gives no discount; and bringing 350, 200, and 100 last gives an additional discount of 100, for a total discount of 350.

Your task is to find the maximum total discount Lindsay can obtain by choosing how to group the items she brings to the counter. Every time three items are placed on the counter together, the cheapest of the three is free; items left over in groups of fewer than three receive no discount.

The first line contains the number of test scenarios $t$ ($1 \le t \le 20$). Each scenario consists of two lines. The first line gives the number of items Lindsay is buying, $n$ ($1 \le n \le 20000$). The next line gives the prices of these items $p_i$, separated by spaces ($1 \le p_i \le 20000$).

For each scenario, output on its own line the maximum discount Lindsay can get by choosing which items she brings to the counter together.