Non-Adjacent Flip

时间限制：2s
空间限制：1024MB

题目描述

有 $N$ 枚编号为 $1$ 到 $N$ 的硬币。长度为 $N$ 的二进制字符串 $S$ 描述它们的状态：1 表示正面朝上，0 表示反面朝上。

一次操作可以选择满足 $1\le i<j\le N$ 且 $j-i\ge 2$ 的两个位置，同时翻转这两枚硬币。请判断能否使所有硬币都反面朝上；若可以，求最少操作次数，否则输出 $-1$。

你需要处理 $T$ 组测试数据。

输入格式

第一行输入整数 $T$。

每组数据包含两行：第一行是整数 $N$，第二行是长度为 $N$ 的二进制字符串 $S$。

输出格式

对每组数据输出一行答案。

样例输入 1

5
3
101
6
101101
5
11111
6
000000
30
111011100110101100101000000111

样例输出 1

1
2
-1
0
8

数据范围

• $1\le T\le 2\times 10^5$；
• $3\le N\le 2\times 10^5$；
• $S$ 是长度为 $N$ 的二进制字符串；
• 单个输入文件内所有测试用例的 $N$ 之和不超过 $2\times 10^5$。