题目描述

故障机器人有一个长度为 $n$ 的字符串 $s$，只包含字母 a 和 b。他想从字符串中删除一段（可能长度为 $0$）连续的字符，使得剩下的字符串中字符 a 和 b 的数量相等。删除的连续子串可以从字符串 $s$ 的任意位置开始。

故障机器人很喜欢他的字符串 $s$，因此他希望删除的连续字符尽可能少。

请你计算：为了使剩余字符串中 a 与 b 的数量相等，最少需要删除多少个连续字符。如果必须删除所有字符（即使字符串变为空）才能满足条件，则输出 $-1$。

输入格式

第一行包含一个整数 $t$（$1\le t\le 10^4$）— 测试用例的数量。

每个测试用例包含两行：

• 第一行包含一个整数 $n$（$2\le n\le 2\times 10^5$），表示字符串 $s$ 的长度；
• 第二行包含一个长度为 $n$ 的字符串 $s$，只可能包含字母 a 和 b。

额外保证：所有测试用例中 $n$ 的总和不超过 $2\times 10^5$。

输出格式

对于每个测试用例，输出一行：

• 若必须删除所有字符才能使得剩余字符串中 a 与 b 数量相等，输出 -1；
• 否则输出一个非负整数，表示最少需要删除的连续字符个数。

样例输入

5
5
bbbab
6
bbaaba
4
aaaa
12
aabbaaabbaab
5
aabaa

样例输出

3
0
-1
2
-1

说明

样例解释

• 样例 $1$：删除前 $3$ 个字符后，字符串变为 "ab"，其中各 $1$ 个 a 和 b，因此答案为 $3$。
• 样例 $2$：原字符串中 a 与 b 数量已相等，故无需删除，答案为 $0$。
• 样例 $3$ 与 $5$：必须删除所有字符才能得到等量的 a 与 b，因此输出 $-1$。
• 样例 $4$：例如删除第 $5$ 和第 $6$ 个字符，剩下字符串为 "aabbabbaab"，其中 a 与 b 的数量均为 $5$，因此最少删除数为 $2$。