题目描述

有一个长为 $N$ 的01字符串 $S$。你可以对 $S$ 进行下述操作任意多次 选择一对整数 $i, j$ 满足 $1 \le i < j \le N$ 且 $j - i \ge 2$。翻转 $S_i$ 和 $S_j$。

翻转是说 0 变 1，1 变 0。

判断是否可能把 $S$ 里字符都变成 0。若可能，求出所需的最少操作次数。

一个输入文件里有 $T$ 组测试数据。 限制

	$1≤T≤2×10^5$

	$3≤N≤2×10^5$

	一个输入文件里的所有测试数据的 $N$ 值和不超过 $2\times 10^5$。

输入格式

$T$

$测试_1$

$测试_2$

$\vdots$

$测试_T$ 一个测试的格式是

$N$

$S$

输出格式

输入 $T$ 行。第 $i$ 行是第 $i$ 个测试的答案，若可能把 $S$ 里字符都变成 0，输出所需的最少操作次数，否则输出 -1。

5

3

101

6

101101

5

11111

6

000000

30

111011100110101100101000000111

1

2

-1

0

8