A14765 | Dominant Character

Ashish has a string $s$ of length $n$ containing only characters 'a', 'b' and 'c'.

He wants to find the length of the smallest substring, which satisfies the following conditions:

- Length of the substring is at least $2$
- 'a' occurs strictly more times in this substring than 'b'
- 'a' occurs strictly more times in this substring than 'c'

Ashish is busy planning his next Codeforces round. Help him solve the problem.

A string $a$ is a substring of a string $b$ if $a$ can be obtained from $b$ by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

The first line contains a single integer $t$ $(1 \le t \le 10^{5})$ — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $n$ $(2 \le n \le 10^{6})$ — the length of the string $s$ .

The second line of each test case contains a string $s$ consisting only of characters 'a', 'b' and 'c'.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^{6}$ .

For each test case, output the length of the smallest substring which satisfies the given conditions or print $-1$ if there is no such substring.