C-小红的好01串修改_牛客周赛 Round 102

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 小红定义一个仅由字符 $\texttt{`0'}$ 和 $\texttt{`1'}$ 组成的字符串（简称 01 串）为好 01 串，当且仅当：任意两个相邻的字符都是不同的。

$\hspace{15pt}$ 现在，小红拿到了一个长为 $n$ 的 01 串，他想要将其变成一个好 01 串。为此，他可以进行以下操作：
$\hspace{23pt}\bullet\,$ 选择两个相邻的字符（长度为 $2$ 的子串），将它们反置（若原字符为 $\texttt{`1'}$ ，反置后为 $\texttt{`0'}$ ；若原字符为 $\texttt{`0'}$ ，反置后为 $\texttt{`1'}$ ）。

$\hspace{15pt}$ 小红想知道是否能将原串变为好 01 串，如果可以，最少需要进行几次操作。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：
第一行输入一个整数 ，代表字符串长度。
第二行输入一个长度为  的 01 串 。

除此之外，保证单个测试文件的  之和不超过 。

输出描述:

对于每一组测试数据，新起一行，输出一个整数，代表在规定操作下将原字符串变为好 01 串所需的最少操作次数；若无法实现，则输出 。

示例1

输入

复制

输出

复制

0
2
-1

说明

对于第一组测试数据，原 01 串已经是好 01 串，不需要操作。

对于第二组测试数据，其中一种最优操作方案是：
选择第二个和第三个字符修改，字符串变为 ；
选择第一个和第二个字符修改，字符串变为 ，此时是好 01 串。