F. Fiesta in the Mountains
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

For the third time, Pacha invites you to walk through the mountains. You are very scared to go because the last time you went, you got lost on the way back and almost fell off a cliff. But since you are an adrenaline junkie, you decide to go again. Pacha provides you with a map with $$$n$$$ segments, starting from segment $$$1$$$ and ending at segment $$$n$$$, where the height of each segment is indicated. If there is a difference between segments, then you have to exert effort depending on the difference in heights. This time you decide to take your girlfriend with you, and since you are a simp, you decide to carry her backpack for her. So now the climbs require much more effort than before.

The effort between two consecutive segments $$$i$$$ and $$$i+1$$$ is defined as:

You realize that it is very difficult and you feel like crying, but luckily another time traveler appears in front of you. He tells you that in the future, Cochabamba is the most advanced city in the world thanks to the multiple programming contests held every year.

he programmers who participated in the "Cocha, We Are Innovation" contest in 2881 developed a device that, if you are currently on segment $$$i$$$, lets you teleport to the next segment $$$(i + 1)$$$ or the one after the next $$$(i + 2)$$$ without any effort. Being the 3.0 version, it can be used as many times as you want, but once you teleport, you must proceed to the next segment—meaning if you land on segment $$$i$$$, you must still move on to segment $$$i + 1$$$ and exert the required effort, unless you've teleported onto the very last segment.

Now you must calculate the minimum effort you can make if you use the device wisely.

Input

The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 2.5 * 10^4$$$) representing the number of test cases.

For each test case, the first line contains an integer $$$n$$$ ($$$4 \leq n \leq 10^5$$$) representing the number of segments. The second line contains $$$n$$$ integers $$$h_i$$$ ($$$1 \leq h_i \leq 10^4$$$) representing the height of each segment.

It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$10^5$$$.

Output

For each test case, an integer representing the minimum effort you can make if you use the teleportation device wisely.

Example
Input
3
5
1 2 3 4 5
7
1 3 2 5 1 4 2
4
1 10 1 1
Output
3
5
0