题目描述

有 $N$ 枚编号为 $1$ 到 $N$ 的硬币，每枚硬币有正反两面，可以区分。硬币的正反面状态由一个长度为 $N$ 的字符串 $S$ 表示，$S$ 的第 $i$ 个字符为 1 时表示第 $i$ 枚硬币正面朝上，为 0 时表示反面朝上。

你可以进行如下操作，次数不限（可以为 $0$ 次）：

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

请判断是否可以通过若干次操作将所有硬币都翻到反面。如果可以，请求出所需操作次数的最小值；如果不可以，输出 $-1$。

有 $T$ 组测试数据，请分别作答。

输入格式

输入通过标准输入给出，格式如下：

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

每组数据格式如下：

$N$ $S$

输出格式

输出共 $T$ 行。对于第 $i$ 个测试用例，如果可以通过操作将所有硬币都翻到反面，输出最小操作次数；否则输出 $-1$。

样例 1

输入

5
3
101
6
101101
5
11111
6
000000
30
111011100110101100101000000111

输出

1
2
-1
0
8

说明/提示

限制

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

样例解释 1

对于第 $1$ 个测试用例，选择 $(i, j)=(1, 3)$ 操作 $1$ 次即可将所有硬币翻到反面。对于第 $2$ 个测试用例，先选择 $(i, j)=(1, 3)$ 操作 $1$ 次，再选择 $(i, j)=(4, 6)$ 操作 $1$ 次，共需 $2$ 次操作。对于第 $3$ 个测试用例，无法将所有硬币翻到反面，应输出 $-1$。对于第 $4$ 个测试用例，所有硬币已是反面，无需操作。

由 ChatGPT 4.1 翻译