A circular array 𝑏

of length 𝑚

is nice if every element has at least one adjacent element

∗

that is equal to it. Formally, for every 1≤𝑖≤𝑚

, at least one of the following holds: 𝑏

𝑖

=𝑏

(𝑖+𝑚−2)mod𝑚+1

, or 𝑏

𝑖

=𝑏

𝑖mod𝑚+1

, where 𝑥mod𝑦

denotes the remainder from dividing 𝑥

by 𝑦

.

You are given a circular array 𝑎

of length 𝑛

. In one operation, you may increase or decrease any element of 𝑎

by 1

. Your task is to determine the minimum number of operations required to make array 𝑎

nice. More formally, find the minimum value of ∑

𝑛

𝑖=1

|𝑏

𝑖

−𝑎

𝑖

|

among all nice circular arrays 𝑏

of length 𝑛

.

∗

In a circular array of length 𝑚

:

For each index 2≤𝑖≤𝑚−1
, the element at index 𝑖
is adjacent to the elements at indices 𝑖−1
and 𝑖+1
.
The element at index 1
is adjacent to the elements at indices 2
and 𝑚
.
The element at index 𝑚
is adjacent to the elements at indices 𝑚−1
and 1
.

Input

Each test contains multiple test cases. The first line contains the number of test cases 𝑡

(1≤𝑡≤10

4

). The description of the test cases follows.

The first line of each test case contains a single integer 𝑛

(3≤𝑛≤2⋅10

5

) — the length of the circular array 𝑎

.

The second line of each test case contains 𝑛

integers 𝑎

1

,𝑎

2

,…,𝑎

𝑛

(1≤𝑎

𝑖

≤10

9

) — the elements of the circular array 𝑎

.

It is guaranteed that the sum of 𝑛

over all test cases does not exceed 2⋅10

5

.

Output

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

nice.

Example

Input

Copy

4
5
1 1 1 1 1
4
2 100 99 3
5
2 2 5 9 5
6
1 1 1 2 1 2

Output

Copy

Note

In the first test case, all elements of 𝑎

are equal. Therefore, the circular array 𝑎

is already nice and no operations are required.

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

Increase 𝑎
1
by 1
. Now, 𝑎=[3,100,99,3]
.
Decrease 𝑎
2
by 1
. Now, 𝑎=[3,99,99,3]
.

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

𝑎
1
is equal to 𝑎
4
.
𝑎
2
is equal to 𝑎
3
.
𝑎
3
is equal to 𝑎
2
.
𝑎
4
is equal to 𝑎
1
.

In the third test case, the circular array 𝑎

can become nice by decreasing 𝑎

4

four times. This results in 𝑎=[2,2,5,5,5]

which is nice as every element has at least one adjacent element with the same value.

Codeforces Round 1057

Round Problems