У Монокарпа есть строка $$$s$$$ длины $$$n$$$, состоящая из букв «a» и «b». Он хочет удалить из своей строки некоторое (возможно, нулевое) количество подряд идущих букв таким образом, чтобы в получившейся строке количество букв «a» и «b» стало одинаковым. Начинать удалять буквы Монокарп может с любой позиции строки $$$s$$$.
Монокарпу очень нравится его строка $$$s$$$, поэтому он хочет удалить как можно меньше подряд идущих букв из своей строки.
Перед вами стоит задача определить минимальное количество подряд идущих букв строки $$$s$$$, которые нужно удалить, чтобы количество букв «a» и «b» в получившейся строке стало одинаковым. Если для этого нужно удалить все буквы строки $$$s$$$ (то есть сделать её пустой), сообщите об этом.
В первой строке задано целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
Каждый набор входных данных состоит из двух строк:
Дополнительное ограничение на входные данные: сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите ответ следующим образом:
Если для того, чтобы количество букв «a» и «b» стало одинаковым, нужно удалить все буквы из строки $$$s$$$, выведите $$$-1$$$.
В противном случае выведите минимальное количество подряд идущих букв, которые Монокарпу нужно удалить из своей строки $$$s$$$, чтобы количество букв «a» и «b» стало одинаковым.
55bbbab6bbaaba4aaaa12aabbaaabbaab5aabaa
30-12-1
В первом примере Монокарпу нужно удалить первые три буквы из своей строки. После этого его строка станет равна «ab». В этой строке по одной букве «a» и «b».
Во втором примере в заданной строке по три буквы «a» и «b», поэтому удалять ничего не нужно.
В третьем примере нужно удалить все буквы строки, так как в ней нет ни одной буквы «b», поэтому нужно вывести $$$-1$$$.
В четвертом примере Монокарп может, например, удалить из своей строки пятую и шестую буквы. Тогда его строка станет равна «aabbabbaab». В этой строке по пять букв «a» и «b».
В пятом примере нужно удалить все буквы строки, чтобы сделать равным количество букв «a» и «b», поэтому нужно вывести $$$-1$$$.
