D. Triterminant
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Let $$$b_1, b_2, \dots, b_{n}$$$ be a sequence of integers. A sequence of polynomials $$$A_1,A_2,\dots,A_n$$$ is defined as

$$$$$$ A_k(x) = \det \begin{bmatrix} x & b_1 & 0 & \dots & 0 \\ 1 & x & b_2 & \dots & 0 \\ 0 & 1 & x & \cdot & \vdots \\ \vdots & \vdots & \cdot & \ddots & b_{k} \\ 0 & 0 & \dots & 1 & x \end{bmatrix} $$$$$$

We call $$$b_1, b_2, \dots, b_{n}$$$ good if for all $$$k$$$, all coefficients of $$$A_k$$$ do not exceed $$$1$$$ by the absolute value.

You're given a sequence $$$c_1,c_2,\dots,c_n$$$ such that $$$c_k \in\{-1,1\}$$$. You can change any number $$$c_k$$$ to $$$-c_k$$$.

What is the minimum numbers of the sequence elements you should change to get a good sequence?

Input

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$).

The second line contains $$$n$$$ integers $$$c_1,c_2,\dots,c_n$$$ ($$$c_k$$$ is either $$$-1$$$ or $$$1$$$).

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

Output

For each test case, output the minimum number of $$$c_1,c_2,\dots,c_n$$$ elements that must be changed to obtain a good sequence.

If there is no valid way to obtain a good sequence from $$$c_1, c_2, \dots, c_n$$$, output a single integer $$$-1$$$.

Example
Input
3
4
1 1 1 1
2
1 -1
5
-1 1 1 1 -1
Output
2
0
2
Note

$$$c = (1, -1, 1, -1)$$$ is a good sequence and can be obtained from $$$(1, 1, 1, 1)$$$ in $$$2$$$ changes.