该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

红石线路重构

题目背景

$Fusheng$ 是一位热衷于红石科技的 $Minecraft$ 玩家。某天，他在地下矿洞中发现了一条古老的红石电路线路。

这条线路由 $n$ 个红石中继器串联而成，每个中继器有两种状态：

• 0 表示红石信号未激活（暗淡状态）
• 1 表示红石信号已激活（发光状态）

由于年代久远，这条电路已经部分损坏。$Fusheng$ 想要修复它，使整条线路达到统一状态——要么全部激活（全$1$），要么全部关闭（全$0$）。

幸运的是，$Fusheng$ 在附近找到了一些红石比较器和红石火把。利用这些道具，他可以对电路的某个区间进行"多数原则修复"：

1. 红石比较器修复：选择区间 $[i, j]$，如果该区间内激活的中继器（$1$）数量多于未激活的（$0$），就可以用强信号将整个区间都激活为 $1$。
2. 红石火把反转修复：选择区间 $[i, j]$，如果该区间内未激活的中继器（$0$）数量多于激活的（$1$），就可以切断信号将整个区间都关闭为 $0$。

每次使用道具进行修复都会增加 $Fusheng$ 收集材料的时间。他想知道：最少需要使用多少次道具才能让整条红石线路达到统一状态？

如果无论如何都无法修复，请输出 $-1$（可能需要求助$SuAnderder$获取更高级的红石科技）。

题目描述

$Fusheng$ 有一个长度为$n$的字符串$S$，仅包含$0$和$1$两种字符。

$Ta$ 每次可以选择两个索引 $i$ 和 $j$ $(1\leq i＜j\leq n)$，并满足以下条件之一：

1、如果区间$[i,j]$​中$1$的数量大于$0$的数量，可以把此区间的所有数字都变成$1$。

2、如果区间$[i,j]$中$0$的数量大于$1$的数量，可以把此区间的所有数字都变成$0$。

他想知道把整个串变成全$0$或者全$1$的最少操作次数，如果无解，输出$-1$。

输入格式

第一行包含一个整数 $T$，表示测试用例组数（$1 ≤ T ≤ 20$）

第二行包含两部分，前半部分一个整数 $n$，表示字符串长度，后半部分为长度为$n$的字符串$S$，保证输入只含有$0$、$1$。

（$1 ≤ n ≤ 2 \times 10^5$）

输出格式

每行一个整数表示最少操作次数，若无解则输出$-1$

示例数据

输入样例：

2
3 011
2 11

输出样例：

1
0

样例解释：

• 第一组：初始状态 "011"，选择区间 $[1, 3]$，由于该区间有 $2$ 个 $1$ 和 $1$ 个 $0$，$1$ 的数量更多，可以将整个区间变为 "111"，操作 $1$ 次完成。
• 第二组：初始状态 "11"，已经是全 $1$ 状态，无需操作，答案为 $0$。

限制

• 时间限制：1000ms
• 内存限制：256MB