题目描述

你有 $N$ 个硬币，每个硬币要么朝上（用 1 表示），要么朝下（用 0 表示）。

每次你可以选择一对数 $(i,j)$ 满足

• $1≤i<j≤N$
• $j-i \ge 2$

并把第 $i$ 和 第 $j$ 个硬币翻转，问最后能否使所有硬币朝下。如果可以，输出翻转次数，否则输出 -1。

输入格式

共有 $T$ 组子测试样例。

对于每组测试样例，第一行一个整数 $N$，表示硬币个数。第二行一个字符串 $S$ 描述了这 $N$ 个硬币。

输出格式

输出 $T$ 行。 每行一个整数或者 -1。

5
3
101
6
101101
5
11111
6
000000
30
111011100110101100101000000111

1
2
-1
0
8

数据范围

$1 \le T \le 2\times 10^5$

$3 \le N \le 2\times10^5$

$3 \le \sum N \le 2\times10^5$