题目描述

我们有 $N$ 枚编号为 $1$ 到 $N$ 的硬币，硬币有两个可区分的面。字符串 $S$ 表示硬币的当前状态。如果 $S$ 的第 $i$ 个字符是 1，则表示第 $i$ 枚硬币正面朝上；如果该字符是 0，则表示第 $i$ 枚硬币反面朝上。

你可以重复执行以下操作零次或多次：

• 选择一对整数 $(i,j)$，满足 $1\leq i < j\leq N$ 且 $j-i\geq 2$。翻转第 $i$ 枚硬币和第 $j$ 枚硬币。

确定是否可以使所有 $N$ 枚硬币都反面朝上。如果可能，找到所需操作的最小次数。

给定 $T$ 个测试用例进行求解。

约束条件

• $1 \leq T \leq 2\times 10^5$
• $3 \leq N \leq 2\times 10^5$
• $S$ 是长度为 $N$ 的字符串，由 0 和 1 组成。
• 输入中的所有值均为整数。
• 对于每个输入文件，测试用例的 $N$ 的总和不超过 $2\times 10^5$。

输入

输入以以下格式从标准输入读取：

$T$ $\mathrm{case}_1$ $\vdots$ $\mathrm{case}_T$

每个测试用例的格式如下：

$N$ $S$

输出

输出 $T$ 行。第 $i$ 行 $(1\leq i \leq T)$ 应包含如果可能的话使所有硬币反面朝上所需的最小操作次数，否则输出 -1。

示例输入 1

5
3
101
6
101101
5
11111
6
000000
30
111011100110101100101000000111

示例输出 1

1
2
-1
0
8

对于第一个测试用例，你可以执行操作 $(i,j)=(1,3)$，在一次操作中将所有硬币都翻转成反面朝上。

对于第二个测试用例，你可以先执行操作 $(i,j)=(1,3)$，然后再执行操作 $(i,j)=(4,6)$，在两次操作中将所有硬币都翻转成反面朝上。

对于第三个测试用例，你可以证明无法通过任何操作将所有硬币都翻转成反面朝上，因此应输出 -1。

对于第四个测试用例，硬币已经是反面朝上的状态，所以不需要进行任何操作。