CF1678B1.Tokitsukaze and Good 01-String (easy version)

This is the easy version of the problem. The only difference between the two versions is that the harder version asks additionally for a minimum number of subsegments.

Tokitsukaze has a binary string $s$ of length $n$, consisting only of zeros and ones, $n$ is even.

Now Tokitsukaze divides $s$ into the minimum number of contiguous subsegments, and for each subsegment, all bits in each subsegment are the same. After that, $s$ is considered good if the lengths of all subsegments are even.

For example, if $s$ is "11001111", it will be divided into "11", "00" and "1111". Their lengths are $2$, $2$, $4$ respectively, which are all even numbers, so "11001111" is good. Another example, if $s$ is "1110011000", it will be divided into "111", "00", "11" and "000", and their lengths are $3$, $2$, $2$, $3$. Obviously, "1110011000" is not good.

Tokitsukaze wants to make $s$ good by changing the values of some positions in $s$. Specifically, she can perform the operation any number of times: change the value of $s_i$ to '0' or '1'($1 \leq i \leq n$). Can you tell her the minimum number of operations to make $s$ good?

这是该问题的简单版本。两个版本的唯一区别在于，困难版本额外要求子段的最少数量。

Tokitsukaze 有一个长度为 $n$ 的二进制字符串 $s$，仅由 '0' 和 '1' 组成，且 $n$ 为偶数。

现在，Tokitsukaze 将 $s$ 划分为最少数量的连续子段，使得每个子段内的所有字符均相同。之后，若所有子段的长度均为偶数，则称 $s$ 是“好的”。

例如，若 $s$ 为 "11001111"，则它将被划分为 "11"、"00" 和 "1111"。它们的长度分别为 $2$、$2$、$4$，均为偶数，因此 "11001111" 是“好的”。再举一例，若 $s$ 为 "1110011000"，则它将被划分为 "111"、"00"、"11" 和 "000"，其长度分别为 $3$、$2$、$2$、$3$。显然，"1110011000" 不是“好的”。

Tokitsukaze 希望通过对 $s$ 中某些位置的字符进行修改，使其变为“好的”。具体而言，她可以执行任意次数的操作：将 $s_i$（其中 $1 \leq i \leq n$）的值改为 '0' 或 '1'。你能告诉她使 $s$ 变为“好的”所需的最少操作次数吗？

The first contains a single positive integer $t$ ($1 \leq t \leq 10\,000$) — the number of test cases.

For each test case, the first line contains a single integer $n$ ($2 \leq n \leq 2 \cdot 10^5$) — the length of $s$, it is guaranteed that $n$ is even.

The second line contains a binary string $s$ of length $n$, consisting only of zeros and ones.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

第一行包含一个正整数 $t$（$1 \leq t \leq 10\,000$）—— 测试用例的数量。

对于每个测试用例，第一行包含一个整数 $n$（$2 \leq n \leq 2 \cdot 10^5$）—— 字符串 $s$ 的长度，保证 $n$ 为偶数。

第二行包含一个长度为 $n$ 的二进制字符串 $s$，仅由字符 0 和 1 组成。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

For each test case, print a single line with one integer — the minimum number of operations to make $s$ good.

对于每个测试用例，输出一行，包含一个整数——使 $s$ 变为“好字符串”所需的最少操作次数。

In the first test case, one of the ways to make $s$ good is the following.

Change $s_3$, $s_6$ and $s_7$ to '0', after that $s$ becomes "1100000000", it can be divided into "11" and "00000000", which lengths are $2$ and $8$ respectively. There are other ways to operate $3$ times to make $s$ good, such as "1111110000", "1100001100", "1111001100".

In the second, third and fourth test cases, $s$ is good initially, so no operation is required.

在第一个测试用例中，使 $s$ 变为“好串”的一种方式如下：

将 $s_3$、$s_6$ 和 $s_7$ 改为 '0'，此时 $s$ 变为 "1100000000"，它可以被划分为 "11" 和 "00000000"，其长度分别为 $2$ 和 $8$。还有其他花费 $3$ 次操作使 $s$ 变为“好串”的方法，例如 "1111110000"、"1100001100"、"1111001100"。

在第二、第三和第四个测试用例中，$s$ 初始即为“好串”，因此无需任何操作。