CF1437B.Reverse Binary Strings

You are given a string $s$ of even length $n$. String $s$ is binary, in other words, consists only of 0's and 1's.

String $s$ has exactly $\frac{n}{2}$ zeroes and $\frac{n}{2}$ ones ($n$ is even).

In one operation you can reverse any substring of $s$. A substring of a string is a contiguous subsequence of that string.

What is the minimum number of operations you need to make string $s$ alternating? A string is alternating if $s_i \neq s_{i + 1}$ for all $i$. There are two types of alternating strings in general: 01010101... or 10101010...

给你一个长度为偶数 $n$ 的字符串 $s$。字符串 $s$ 是二进制的，即仅由字符 0 和 1 组成。

字符串 $s$ 恰好包含 $\frac{n}{2}$ 个 0 和 $\frac{n}{2}$ 个 1（$n$ 为偶数）。

在一次操作中，你可以翻转 $s$ 的任意一个子串。字符串的子串是指该字符串的一个连续子序列。

你需要多少次最少的操作次数，才能使字符串 $s$ 变为交替字符串？若对所有 $i$ 均满足 $s_i \neq s_{i + 1}$，则称该字符串为交替字符串。通常存在两种交替字符串：01010101... 或 10101010...

The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($2 \le n \le 10^5$; $n$ is even) — the length of string $s$.

The second line of each test case contains a binary string $s$ of length $n$ ($s_i \in$ {0, 1}). String $s$ has exactly $\frac{n}{2}$ zeroes and $\frac{n}{2}$ ones.

It's guaranteed that the total sum of $n$ over test cases doesn't exceed $10^5$.

第一行包含一个整数 $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$。

For each test case, print the minimum number of operations to make $s$ alternating.

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

In the first test case, string 10 is already alternating.

In the second test case, we can, for example, reverse the last two elements of $s$ and get: 0110 $\rightarrow$ 0101.

In the third test case, we can, for example, make the following two operations:

1. 11101000 $\rightarrow$ 10101100;
2. 10101100 $\rightarrow$ 10101010.

在第一个测试用例中，字符串 10 已经是交替的。

在第二个测试用例中，例如，我们可以反转 $s$ 的最后两个元素，得到：0110 $\rightarrow$ 0101。

在第三个测试用例中，例如，我们可以执行以下两次操作：

1. 11101000 $\rightarrow$ 10101100；
2. 10101100 $\rightarrow$ 10101010。