Sorting the Barbells

The gym at Health University has $N$ barbells of pairwise different weights, each resting on its own rack. In the morning the staff line them up from the lightest to the heaviest so that visitors can find what they need, as in the figure below. (The figure shows the case $N = 5$.)

By closing time, though, the $N$ barbells sit in a jumbled order that has nothing to do with weight. Here is one such arrangement.

Hyunwoo manages the gym, and at closing time he sorts the jumbled barbells into increasing order of weight. The barbells are heavy, so he wants the total weight he lifts to be as small as possible. For safety he never carries two barbells at once. He can move a barbell in three ways.

• Take a barbell off its rack and put it on the gym floor.
• Move a barbell from its rack to an empty rack.
• Move a barbell from the gym floor to an empty rack.

Every move adds the weight of the moved barbell to the total. Suppose three barbells sit on the racks in the order 5kg, 4kg, 1kg. Sorting them in the following order gives a total moved weight of 7kg. First move the 1kg barbell to the gym floor, then move the 5kg barbell onto the rack the 1kg barbell just left. Finally move the 1kg barbell from the floor to the rack where the 5kg barbell started.

Read from standard input. The input holds $T$ ($1 \le T \le 10$) test cases. The first line has the number of test cases $T$. Each test case takes two lines. The first line has the number of barbells $N$, a positive integer at most 1,000. The second line has the weights of the $N$ barbells in the order they sit on the racks. The weights are all different.

Write to standard output. For each test case print, on its own line, the smallest total moved weight needed to sort the barbells in increasing order of weight.