01环

Problem Description

给定一个由字符 '0' 和 '1' 组成的长度为 $N$ 的环形字符串，其中 $N$ 是一个偶数。你可以通过以下两种操作将这个环调整为 $01$ 交替的形式（即相邻字符不相同，如 "0101..." 或 "1010..."）：

• 交换操作：选择任意一个位置 $i$，交换 $i$ 和 $~(i \bmod N) + 1$ 位置的字符（即相邻位置交换，环的首尾也视为相邻）。
• 翻转操作：选择任意一个位置 $i$，将该位置的字符取反（'0' 变 '1'，'1' 变 '0'）。 你的任务是计算出将给定环形字符串转换为 $01$ 交替环所需的最少操作次数。

Input

第一行包含一个整数 $T$（$1 \leq T \leq 10^4$），表示测试用例的数量。 每组测试用例包含两行：

• 第一行为一个偶数 $N$（$2 \leq N \leq 10^6$），表示环形字符串的长度。
• 第二行为一个长度为 $N$ 的字符串 $s$，仅由字符 '0' 和 '1' 组成。 保证所有测试用例的 $N$ 之和不超过 $10^6$。

Output

对于每组测试用例，输出一行一个整数，表示所需的最少操作次数。

Sample Input

2
4
0110
6
000000

Sample Output

1
3

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（3）