CF1437B Reverse Binary Strings

给定一个长度为 $n$ 的字符串 $s$，其中 $n$ 是偶数。字符串 $s$ 是二进制串，也就是说只包含 $0$ 和 $1$。 字符串 $s$ 恰好包含 $\frac{n}{2}$ 个 $0$ 和 $\frac{n}{2}$ 个 $1$（$n$ 是偶数）。 每次操作，你可以翻转 $s$ 的任意一个子串。子串是字符串中一段连续的子序列。 你需要的最少操作次数是多少，才能将字符串 $s$ 变为交错字符串？如果对于所有 $i$，都有 $s_i \neq s_{i+1}$，则称字符串是交错的。一般来说，交错字符串有两种类型：01010101... 或 10101010...

第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 10^5$，$n$ 是偶数），表示字符串 $s$ 的长度。 每个测试用例的第二行包含一个长度为 $n$ 的二进制字符串 $s$（$s_i \in \{0, 1\}$）。字符串 $s$ 恰好包含 $\frac{n}{2}$ 个 $0$ 和 $\frac{n}{2}$ 个 $1$。 保证所有测试用例中 $n$ 的总和不超过 $10^5$。

对于每个测试用例，输出将 $s$ 变为交错字符串所需的最少操作次数。

在第一个测试用例中，字符串 10 已经是交错的。 在第二个测试用例中，例如可以翻转 $s$ 的最后两个字符，得到：0110 $\rightarrow$ 0101。 在第三个测试用例中，例如可以进行如下两次操作： 1. 11101000 $\rightarrow$ 10101100； 2. 10101100 $\rightarrow$ 10101010。 由 ChatGPT 4.1 翻译