小苯的数字消除
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

\hspace{15pt}小苯有一个长度为 n,仅由字符 \texttt{`0'}\texttt{`1'} 构成的字符串 s。下标从 1 开始。

\hspace{15pt}小苯认为 s 的长度过长,他希望用一些“消除”操作,将 s 的长度变得尽可能短。一次“消除”操作描述为:
\hspace{23pt}\bullet\,如果存在这样的 i \left(1 \leqq i < |s|\right) 满足 s_i = s_{i+1},那么小苯可以将 s_i,s_{i+1} 这两个字符消除,其余的字符按原有顺序拼接起来。换句话说,一次操作过后的字符串变为 s= \texttt{(其中,|s| 用于表示字符串 s 的长度)。

\hspace{15pt}小苯为了最小化 s 的长度,因此在开始“消除”操作之前,他可以进行一些“修改”操作。一次“修改”操作描述为:
\hspace{23pt}\bullet\,选择任意一个位置上的字符,将其改为 \texttt{`0'}\texttt{`1'} 中的任意一种。

\hspace{15pt}现在,小苯想知道,他至少需要先进行几次“修改”操作,才能使得存在这样一种“消除”操作的执行方案,使得 s 的长度不超过 1。请你帮他算一算吧。

输入描述:

\hspace{15pt}每个测试文件均包含多组测试数据。第一行输入一个整数 T\left(1\leqq T\leqq 10^3\right) 代表数据组数,每组测试数据描述如下:
\hspace{15pt}第一行输入一个正整数 n\left(1\leqq n\leqq 10^6\right) 代表字符串 s 的长度。
\hspace{15pt}第二行输入一个长度为 n,仅由字符 \texttt{`0'}\texttt{`1'} 构成的字符串 s

\hspace{15pt}除此之外,保证单个测试文件的 n 之和不超过 10^6

输出描述:

\hspace{15pt}对于每组测试数据,新起一行。输出一个整数,代表至少需要进行的“修改”操作的次数。
示例1

输入

复制
2
7
0101110
4
0000

输出

复制
2
0

说明

\hspace{15pt}对于第一组测试数据,一种可能的最优“修改”方式为:将 s_1s_7 上的字符均修改为 \texttt{`1'}s 变为 \texttt{。随后进行 3 次“消除”操作: 
\hspace{23pt}\bullet\,消除 s_1s_2s 变为:\texttt{
\hspace{23pt}\bullet\,消除 s_2s_3s 变为:\texttt{
\hspace{23pt}\bullet\,消除 s_2s_3s 变为:\texttt{
\hspace{15pt}我们可以证明,至少需要进行 2 次“修改”操作。