Inverted World
题号：NC302627
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

\hspace{15pt}小芳拿到了一个仅由字符 \texttt{0} 和 \texttt{1} 组成的长为 n 的字符串 s，他可以进行任意次如下操作：
\hspace{23pt}\bullet\,选择 s 的一个非空子序列^\texttt{[1]}，该子序列任意两个相邻元素都不相同，将该子序列进行 01 反置^\texttt{[2]}。
\hspace{15pt}小芳想知道，最少需要多少次操作才能使得 s 中任意两个相邻元素都不相同？

【名词解释】
\hspace{15pt}子序列^\texttt{[1]}：从原序列中删除任意个（可以为零，也可以为全部）元素，且保持剩余元素相对顺序不变得到的新序列。
\hspace{15pt}01 反置^\texttt{[2]}：同时将字符串中的 \texttt{0} 变成 \texttt{1}，\texttt{1} 变成 \texttt{0}。

输入描述:

\hspace{15pt}每个测试文件均包含多组测试数据。第一行输入一个整数 T\left(1\leqq T\leqq 10^4\right) 代表数据组数，每组测试数据描述如下：

\hspace{15pt}第一行输入一个整数 n\left(1 \leqq n \leqq 2\times10^5 \right)，代表字符串长度。
\hspace{15pt}第二行输入一个长为 n，仅由字符 \texttt{0} 和 \texttt{1} 构成的字符串 s。

\hspace{15pt}除此之外，保证单个测试文件的 n 之和不超过 2 \times 10^5。

输出描述:

\hspace{15pt}对于每组测试数据，新起一行输出一个整数，代表所需要的最少操作次数。
示例1

输入

复制 
2
5
11101
5
11100

输出

复制 
1
1

说明

\hspace{15pt}对于第一组测试数据，一种可行的操作方法为 1\underline1101\rightarrow 1\underline0101。

\hspace{15pt}对于第二组测试数据，一种可行的操作方法为 1\underline110\underline0\rightarrow1\underline010\underline1。