#P18622. Triterminant

Triterminant

Triterminant

对于整数序列 b1,b2,…,bnb_1,b_2,\ldots,b_n,定义多项式 A1(x),A2(x),…,An(x)A_1(x),A_2(x),\ldots,A_n(x):

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

矩阵大小为 (k+1)×(k+1)(k+1)\times(k+1)。更准确地说,主对角线元素均为 xx,第 ii 个上对角线元素为 bib_i,第 ii 个下对角线元素为 11(1≤i≤k1\le i\le k),其余元素为 00。

如果对所有 1≤k≤n1\le k\le n,Ak(x)A_k(x) 的每个系数的绝对值都不超过 11,则称序列 bb 是好序列。

给定序列 c1,c2,…,cnc_1,c_2,\ldots,c_n,其中每项都是 −1-1 或 11。你可以选择任意若干项,将其符号翻转,即将 ckc_k 改为 −ck-c_k。求使序列变为好序列,至少需要改变多少项。

输入格式

输入包含多组测试数据。

第一行包含测试数据组数 tt,其中 1≤t≤1051\le t\le10^5。

每组测试数据的第一行包含整数 nn,其中 1≤n≤1051\le n\le10^5。

第二行包含 nn 个整数 c1,…,cnc_1,\ldots,c_n,其中 ci∈{−1,1}c_i\in\{-1,1\}。

保证所有测试数据的 nn 之和不超过 10510^5。

输出格式

对每组测试数据,输出一个整数,表示最少需要改变的元素个数。

如果不存在任何方案能将给定序列变为好序列,则输出 −1-1。

样例输入 1

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

样例输出 1

2
0
2

样例说明

(1,−1,1,−1)(1,-1,1,-1) 是一个好序列,可以从 (1,1,1,1)(1,1,1,1) 改变两项得到。