题目描述

有 $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$ ，表示数据组数。

对于每组数据，第一行输入一个整数 $N$ ，表示字符串的长度；第二行输入一个只有 $0$ 和 $1$ 的字符串。

输出格式

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

输入输出样例 #1

输入 #1

5
3
101
6
101101
5
11111
6
000000
30
111011100110101100101000000111

输出 #1

1
2
-1
0
8

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

数据范围

• $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$