D. Not Alone

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

0
2
4
1

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.