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

• 交换操作：选择任意一个位置 $i$，交换 $i$ 和 $(i \bmod N)+1$ 位置的字符（即相邻位置交换，环的首尾也视为相邻）。
• 翻转操作：选择任意一个位置 $i$，将该位置的字符取反（‘0’ 变 ‘1’，‘1’ 变 ‘0’）。

你的任务是计算出将给定环形字符串转换为 $01$ 交替环所需的最少操作次数。

输入格式

第一行包含一个整数 $T$ $(1 \leq T \leq 10^4)$，表示测试用例的数量。

每组测试用例包含两行：

• 第一行为一个偶数 $N$ $(2 \leq N \leq 10^6)$，表示环形字符串的长度。
• 第二行为一个长度为 $N$ 的字符串 $s$，仅由字符 ‘0’ 和 ‘1’ 组成。

保证所有测试用例的 $N$ 之和不超过 $10^6$。

输出格式

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

样例

输入

2
4
0110
6
000000

输出

1
3