题目描述

给定一个长度为 $n$ 的二进制字符串 $s$。

我们称一个字符串是“交替的”，当且仅当它不包含任何相邻的相同字符。例如，0101、1 和 01 是交替字符串，而 0110 不是。

你希望通过执行以下操作任意次（包括 $0$ 次），将 $s$ 转换为一个交替字符串：

• 选择当前字符串中的任意一个字符并将其删除。

但是，你的操作序列必须遵循一个规则：你删除的字符必须严格交替。这意味着如果你上一次删除的是 0，下一次就必须删除 1，反之亦然。你删除的第一个字符可以是 0 也可以是 1。

请计算使 $s$ 变为交替字符串所需的最少操作次数。如果无论如何都无法达到目的，请输出 -1。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 测试用例的数量。

对于每个测试用例：

• 第一行包含一个整数 $n$（$1 \le n \le 2 \times 10^5$）—— 字符串 $s$ 的长度。
• 第二行包含一个长度为 $n$ 的二进制字符串 $s$，仅由字符 0 和 1 组成。

输出格式

对于每个测试用例，输出一行一个整数，表示使 $s$ 变为交替字符串所需的最少操作次数；如果不可能，则输出 -1。

样例输入 1

5
4
0101
3
111
6
100110
6
100010
6
011110

样例输出 1

0
-1
2
3
5

说明

样例解释

• 在第一个测试用例中，字符串 0101 已经是交替的。不需要进行任何操作，因此答案为 $0$。
• 在第二个测试用例中，字符串为 111。为了使其交替，我们最多只能保留一个 1，这就需要删除两个 1。然而，我们的删除操作必须在 0 和 1 之间严格交替。由于我们没有任何 0 可以删除，因此不可能执行两次对 1 的删除。答案为 -1。
• 在第三个测试用例中，字符串为 100110。我们只需删除一个 0 和一个 1 即可消除相邻的重复字符。由于我们恰好删除了一个 0 和一个 1，操作是完全平衡且合法的。剩余的字符串为 1010，恰好需要 $2$ 次操作。
• 在第四个测试用例中，字符串为 100010。为了消除相邻重复字符，我们自然希望删除两个 0 以形成 1010。但是，删除两个 0 和零个 1 违反了严格交替规则（两者的数量之差不能超过 $1$）。为了修复这种不平衡，我们被迫额外从字符串边缘删除一个 1。我们总共删除两个 0 和一个 1（例如按 0, 1, 0 的顺序），留下交替字符串 010。这需要 $3$ 次操作。
• 在第五个测试用例中，字符串为 011110。要消除相邻重复字符，必须删除三个 1。为了达到平衡，我们必须额外删除至少两个 0。由于我们的压缩字符串（忽略重复）为 010，里面只有两个 0（在最外侧两端），我们被迫将它们全部删除，最终只留下一个字符 1。我们删除了三个 1 和两个 0，总共需要 $5$ 次操作。

数据范围

• 对于所有测试点，保证 $1 \le t \le 10^4$。
• 对于每个测试用例，保证 $1 \le n \le 2 \times 10^5$。
• 保证同一测试点内所有测试用例的 $n$ 之和不超过 $2 \times 10^5$。
• 保证字符串 $s$ 仅由字符 0 和 1 组成。