题目描述

活动现场有 $n$ 盏灯，它们的初始状态由一个长度为 $n$ 的二进制字符串 $s$ 表示：

• $s_i=0$ 表示第 $i$ 盏灯熄灭；
• $s_i=1$ 表示第 $i$ 盏灯点亮。

每次操作，你可以选择任意两盏不同的灯，同时翻转它们的状态：点亮的灯变为熄灭，熄灭的灯变为点亮。

你希望最终所有灯都处于点亮状态。请输出最少需要进行的操作次数。如果无法实现，输出 $-1$。

你可以进行零次操作。

输入格式

第一行包含一个整数 $t$ ($1\le t\le10^4$)，表示测试用例的数量。

对于每个测试用例：

• 第一行包含一个整数 $n$ ($1\le n\le2\times10^5$)，表示灯的数量；
• 第二行包含一个长度恰好为 $n$ 的二进制字符串 $s$ ($\forall s_i\in\{0,1\}$)，表示灯的初始状态。

数据保证所有测试用例的 $n$ 之和不超过 $2\times10^5$。

输出格式

对于每个测试用例，输出一行一个整数，表示使所有灯点亮所需的最少操作次数。如果无法实现，输出 $-1$。

6
5
10101
6
010010
4
1111
3
010
3
000
1
0

1
2
0
1
-1
-1

样例解释

第一组测试用例中，选择第 $2$ 盏和第 $4$ 盏灯进行一次操作，就可以使所有灯点亮。

第二组测试用例中，可以先选择第 $1$ 盏和第 $3$ 盏灯，再选择第 $4$ 盏和第 $6$ 盏灯，共进行两次操作。

第三组测试用例中，所有灯已经点亮，无需操作。

第四组测试用例中，选择第 $1$ 盏和第 $3$ 盏灯进行一次操作，就可以使所有灯点亮。选中的两盏灯不必相邻。

第六组测试用例中，只有一盏灯，无法选择两盏不同的灯进行操作。