F. Autobahn Optimization
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You just finished picking the best light bulb for Felseneggweg and are now on your way home on the German Autobahn, which is famous for its absence of a speed limit and super fast cars. Since you are a Junior City Planner, you notice that everyone could arrive at the destination faster and want to stop them from blocking each other. Therefore, you start optimizing which car should go in which lane.

There are $$$n$$$ cars driving on the Autobahn, which currently has only one lane. Since not all cars are the same, the $$$i$$$-th car has a maximum speed of $$$s_i$$$.

Now the cars arrive at a fork, at which the Autobahn splits up into two lanes. Each car can pick one of the two lanes and has to stay there since a barrier splits the lanes.

All cars want to go as fast as possible, but they cannot drive faster than the car in front of them. In particular, if, after the lane split, the car $$$j$$$ drives right in front of the car $$$i$$$ with the speed of $$$c_j$$$, then the $$$i$$$-th car will drive with the speed of $$$c_i = \min(c_j, s_i)$$$. If there is no car in front of the $$$i$$$-th car, then $$$c_i = s_i$$$.

Your task is to distribute the cars into lanes in such a way that the sum of the speed losses is minimized:

$$$$$$\sum_{i=1}^{n} (s_i - c_i) \to \min$$$$$$

What is the least possible sum of speed losses?

Input

The first line of the input contains a single integer $$$t$$$ ($$$1 \leq t \leq 100$$$), the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 1\;000$$$), the number of cars. The cars enter the lanes in the order they are given in the input, and this order cannot be changed.

The second line of each test case contains $$$n$$$ integers $$$s_1,\dots,s_n$$$ ($$$1 \leq s_i \leq 5\;000$$$), the maximum speeds of the cars.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$1\;000$$$.

Output

Print one integer, the least possible sum of speed losses.

Examples
Input
2
5
4 3 8 2 7
5
3 9 10 5 1
Output
0
1
Input
3
6
1 2 3 4 5 6
6
6 1 5 2 4 3
4
1 3 2 4
Output
6
1
2