题目描述

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

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$ 变成好的。具体来说，她可以进行任意次数的操作：将 $s_i$ 的值改为 '0' 或 '1'（$1 \leq i \leq n$）。你能告诉她最少需要多少次操作才能使 $s$ 变成好的吗？

输入格式

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

输出格式

对于每个测试用例，输出一行一个整数，表示将 $s$ 变成好的所需的最小操作次数。

说明/提示

在第一个测试用例中，将 $s_3$、$s_6$ 和 $s_7$ 改为 '0'，此时 $s$ 变为 "1100000000"，可以划分为 "11" 和 "00000000"，长度分别为 $2$ 和 $8$。还有其他操作 $3$ 次使 $s$ 变好的方法，例如 "1111110000"、"1100001100"、"1111001100"。

在第二、第三和第四个测试用例中，$s$ 一开始就是好的，因此不需要任何操作。

由 ChatGPT 4.1 翻译

样例

5
10
1110011000
8
11001111
2
00
2
11
6
100110

3
0
0
0
3