Ashish 有一个长度为 $$$n$$$ 的字符串 $$$s$$$,仅包含字符“a”、“b”和“c”。
他要求最小子串的长度,满足以下条件:
- 子字符串的长度至少为 $$$2$$$
- 'a' 在此子字符串中出现的次数严格多于 'b'
- 'a' 在此子字符串中出现的次数严格多于 'c'
Ashish 正忙于计划他的下一轮 Codeforces。帮助他解决问题。
字符串 $$$a$$$ 是字符串 $$$b$$$ 的子字符串,如果 $$$a$$$ 可以通过从 $$$b$$$ 删除开头的几个(可能是零个或全部)字符和从末尾删除几个(可能是零个或全部)字符来获得。
输入
第一行包含一个整数 $$$t$$$ $$$(1 \le t \le 10^{5})$$$ — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ $$$(2 \le n \le 10^{6})$$$ — 字符串 $$$s$$$ 的长度。
每个测试用例的第二行包含一个字符串 $$$s$$$,仅由字符“a”、“b”和“c”组成。
保证所有测试用例的$$$n$$$总和不超过$$$10^{6}$$$。
输出
对于每个测试用例,输出满足给定条件的最小子串的长度,如果没有这样的子串,则打印 $$$-1$$$。
示例
输入 #1
3 2 aa 5 cbabb 8 cacabccc
输出 #1
2 -1 3
注意
考虑第一个测试用例。在子串“aa”中,“a”出现两次,而“b”和“c”出现零次。由于“a”出现的次数严格多于“b”和“c”,因此子字符串“aa”满足条件,答案为$$$2$$$。子串“a”也满足这个条件,但是它的长度不至少为$$$2$$$。
在第二个测试用例中,可以证明,在“cbabb”的所有子字符串中,“a”出现的次数都不严格多于“b”和“c”。
在第三个测试用例“cacabccc”中,满足条件的最小子串的长度为$$$3$$$。