← 返回题目列表

Codeforces · 1605/C

C. 主导角色

中文机器翻译题面 查看原题

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$$$。