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.

Not Alone

Examples