C. Доминантный характер
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Ashish есть строка $$$s$$$ длины $$$n$$$, содержащая только символы '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$$$, если такой подстроки нет.

Пример
Входные данные
3
2
aa
5
cbabb
8
cacabccc
Выходные данные
2
-1
3
Примечание

Рассмотрим первый набор входных данных. В подстроке «aa», 'a' встречается дважды, а 'b' и 'c' встречаются ноль раз. Поскольку 'a' встречается строго больше раз, чем 'b' и 'c', подстрока «aa» удовлетворяет условию, и ответ равен $$$2$$$. Подстрока «a» также удовлетворяет этому условию, однако ее длина меньше $$$2$$$.

Во втором наборе входных данных можно показать, что ни в одной из подстрок «cbabb» 'a' не встречается строго больше раз, чем 'b' и 'c'.

В третьем наборе входных данных, «cacabccc», длина наименьшей подстроки, удовлетворяющей условиям, равна $$$3$$$.