小苯的数字消除

题号：NC290271
时间限制：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$ 。请你帮他算一算吧。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：
第一行输入一个正整数  代表字符串  的长度。 
第二行输入一个长度为 ，仅由字符  和  构成的字符串 。

除此之外，保证单个测试文件的  之和不超过 。

输出描述:

对于每组测试数据，新起一行。输出一个整数，代表至少需要进行的“修改”操作的次数。

示例1

输入

复制

输出

复制

2
0

说明

对于第一组测试数据，一种可能的最优“修改”方式为：将  和  上的字符均修改为 ， 变为 。随后进行  次“消除”操作： 
消除  和 ， 变为：； 
消除  和 ， 变为：；
消除  和 ， 变为：。 
我们可以证明，至少需要进行  次“修改”操作。