A circular array $b$ of length $m$ is nice if every element has at least one adjacent element$^{\text{∗}}$ that is equal to it. Formally, for every $1\le i\le m$, at least one of the following holds: $b_i = b_{(i+m-2)\bmod m\;+1}$, or $b_i = b_{i\bmod m\;+1}$, where $x \bmod y$ denotes the remainder from dividing $x$ by $y$.

You are given a circular array $a$ of length $n$. In one operation, you may increase or decrease any element of $a$ by $1$. Your task is to determine the minimum number of operations required to make array $a$ nice. More formally, find the minimum value of $\sum_{i=1}^n |b_i - a_i|$ among all nice circular arrays $b$ of length $n$.

$^{\text{∗}}$In a circular array of length $m$: For each index $2\le i\le m - 1$, the element at index $i$ is adjacent to the elements at indices $i - 1$ and $i + 1$. The element at index $1$ is adjacent to the elements at indices $2$ and $m$. The element at index $m$ is adjacent to the elements at indices $m - 1$ and $1$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($3\le n\le 2\cdot 10^5$) — the length of the circular array $a$.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1\le a_i\le 10^9$) — the elements of the circular array $a$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.

Output

For each test case, output a single integer representing the minimum number of operations required to make array $a$ nice.

Note

In the first test case, all elements of $a$ are equal. Therefore, the circular array $a$ is already nice and no operations are required.

In the second test case, we can perform the following sequence of operations:

• Increase $a_1$ by $1$. Now, $a=[3, 100, 99, 3]$.
• Decrease $a_2$ by $1$. Now, $a=[3, 99, 99, 3]$.

After these operations, every element has at least one adjacent element with the same value:

• $a_1$ is equal to $a_4$.
• $a_2$ is equal to $a_3$.
• $a_3$ is equal to $a_2$.
• $a_4$ is equal to $a_1$.

In the third test case, the circular array $a$ can become nice by decreasing $a_4$ four times. This results in $a = [2, 2, 5, 5, 5]$ which is nice as every element has at least one adjacent element with the same value.