Monocarp 有一个长度为 $$$n$$$ 的字符串 $$$s$$$,由字母 ' 组成a' 和 'b'。他想删除一些(可能是零) 连续 字符串中的字母以这样的方式表示字母数 ' 结果字符串中的a' 和 'b' 变得相等。 Monocarp 可以开始删除字符串 $$$s$$$ 中任意位置的字母。
Monocarp 非常喜欢他的字符串 $$$s$$$,因此他想从中删除尽可能少的连续字母。
您的任务是确定字符串 $$$s$$$ 中需要删除的连续字母的最小数量,以便字母数量 ' 结果字符串中的a' 和 'b' 变得相等。如果需要从字符串 $$$s$$$ 中删除所有字母(即,将其设为空),请报告此情况。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例由两行组成:
- 第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — 字符串 $$$s$$$ 中的字符数;
- 第二行包含长度为 $$$n$$$ 的字符串 $$$s$$$,由字母 'a'和/或'b'.
对输入的附加约束:所有测试用例的 $$$n$$$ 值的总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印答案如下:
如果为了使字母数'a' 和 'b'相等,需要去掉字符串$$$s$$$中的所有字母,输出$$$-1$$$。
否则,输出 Monocarp 需要从字符串 $$$s$$$ 中删除的最小连续字母数,以便字母数 'a' 和 'b' 变得相等。
示例
输入复制
55bbbab6bbaaba4aaaa12aabbaaabbaab5aabaa
输出复制
30-12-1
注意
在第一个示例中,Monocarp 需要删除字符串中的前三个字母。之后,他的字符串将变成“ab“。在这个字符串中,有一个字母 'a'和一个字母'b'.
在第二个示例中,给定的字符串包含三个字母 'a'和三个字母'b',所以不需要删除任何内容。
在第三个示例中,需要删除字符串的所有字母,因为没有字母 'b',因此应打印 $$$-1$$$。
在第四个示例中,Monocarp 可以从字符串中删除第五个和第六个字母。那么他的字符串将变成“阿巴巴巴“。该字符串中有五个字母 'a'和五个字母'b'.
在第五个示例中,需要删除字符串的所有字母,以使字母数 'a' 和 'b' 相等,因此应打印 $$$-1$$$。