设 $b_1, b_2, \dots, b_n$ 为一个整数序列。多项式序列 $A_1, A_2, \dots, A_n$ 定义如下：

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

如果对于所有的 $k$，多项式 $A_k$ 的所有系数的绝对值都不超过 1，则称序列 $b_1, b_2, \dots, b_n$ 是“好的”。 给定一个序列 $c_1, c_2, \dots, c_n$，其中 $c_k \in \{-1, 1\}$。你可以将任意数字 $c_k$ 变为 $-c_k$。 为了得到一个好的序列，你最少需要改变多少个序列元素？

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 10^5$)。 接下来是各测试用例的描述。 每个测试用例的第一行包含一个整数 $n$ ($1 \le n \le 10^5$)。 第二行包含 $n$ 个整数 $c_1, c_2, \dots, c_n$（$c_k$ 为 $-1$ 或 $1$）。 保证所有测试用例的 $n$ 之和不超过 $10^5$。

输出格式

对于每个测试用例，输出为了得到一个好的序列，最少需要改变的 $c_1, c_2, \dots, c_n$ 的元素个数。 如果无法通过改变 $c_1, c_2, \dots, c_n$ 得到一个好的序列，则输出 $-1$。

样例

样例输入 1

3
4
1 1 1 1
2
1 -1
5
-1 1 1 1 -1

样例输出 1

2
0
2

说明

$c = (1, -1, 1, -1)$ 是一个好的序列，可以通过改变 $(1, 1, 1, 1)$ 中的 2 个元素得到。