0-1翻转
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

有一个长度为 N 仅由 0 和 1 组成的字符串 S，你可以进行若干次如下操作（也可以是 0 次）：

  • 选择两个相邻的 1 全变成 0 或者选择两个相邻的 0 全变成 1

求将字符串 S 的每一位都变成 0 所需的最小操作次数。

输入描述:

第一行输入一个正整数 T(1 \leq T \leq 2 \times 10^5)，表示数据组数。

接下来输入 2T 行，每组数据两行，先输入一行一个正整数 N(1 \leq N \leq 2 \times 10^5)，表示字符串 S 的长度，接下来输入一行字符串 S（仅包含 0 和 1）。

数据保证 N 的总和不超过 2 \times 10^5。

输出描述:

输出 T 行，对于每组数据，输出一行一个整数表示将字符串 S 的每一位都变成 0 所需的最小操作次数（如果不能实现输出 -1）。
示例1

输入

复制 
3
2
00
3
101
4
1001

输出

复制 
0
-1
3

说明

对于第一组数据，不需要进行任何操作，所以输出 0。

对于第二组数据，无论进行多少次操作都不可能将字符串的每一位都变成 0，所以输出 -1。

对于第三组数据，进行如下 3 次操作 "1001" -> "1111" -> "0011" -> "0000" 后，字符串的每一位都将变成 0，没有比 3 更少的操作次数，所以输出 3。