Problem Description

An array $a$ of length $n$ is said to be wavy, if for each $1 < i < n$ either $a_i > \max \{a_{i-1},a_{i+1}\}$ or $a_i < \min \{a_{i-1},a_{i+1}\}$ holds.

You are given an array $b$ of length $n$ $(1\leq b_i\leq 10^9)$ , consisting of integers. You want to make the array wavy. To do that you can spend some coins, with each coin you can make one element in $b$ increase or decrease by $1$. Calculate the minimum number of coins you need to spend to make the array wavy.

Input

The first line contains the number of test cases $T$ $(1\le T\le 10^3)$.

The first line of each test case contains one integer $n$ $(1\leq n\leq 10^6)$ - the length of array $b$ .

The second line contains $n$ integers $b_1,b_2,\cdots,b_n$ $(1\leq b_i\leq 10^9)$ - the array $b$ .

It's guarantee that the sum of $n$ among all test cases is not greater than $3\times 10^6$ .

Output

For each test case, output one integer, the minimum number of coins you need to spend to make the array wavy.

3
4
1 7 6 5
6
1 2 3 4 5 6
6
1 1 4 5 1 4

2
4
4