C. Баба Капа вяжет шарф
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Баба Капа решила связать шарф и попросила Деда Шера сделать для него шаблон, представляющий собой строку из строчных букв латинского алфавита. Деда Шер написал строку $$$s$$$ длины $$$n$$$.

Баба Капа хочет связать красивый шарф, а по ее мнению красивый шарф можно связать только из строки, являющейся палиндромом. Она хочет изменить шаблон, написанный Дедой Шером, но, чтобы его сильно не обидеть, она выберет одну любую строчную букву латинского алфавита и уберет какие-то (на свой выбор, возможно никакие или все) вхождения этой буквы в строку $$$s$$$.

При этом она хочет, чтобы количество удаленных из шаблона символов было как можно меньше. Помогите ей и скажите, какое минимальное количество символов она может удалить, чтобы строка $$$s$$$ стала палиндромом, или скажите, что это невозможно. Заметьте, что она может удалять только символы, равные одной букве, которую она выбрала.

Строка называется палиндромом, если она одинаково читается слева направо и справа налево. Например, строки 'kek', 'abacaba', 'r' и 'papicipap' — палиндромы, а строки 'abb' и 'iq' — нет.

Входные данные

Первая строка содержит единственное целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных. Следующие $$$2 \cdot t$$$ строк содержат описание наборов входных данных. Описание каждого набора входных данных состоит из двух строк.

Первая строка описания каждого набора входных данных содержит единственное целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — длину строки.

Вторая строка описания каждого набора входных данных содержит строку $$$s$$$ из $$$n$$$ строчных букв латинского алфавита.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите минимальное количество символов, которое потребуется удалить Бабе Капе, чтобы строка стала палиндромом, если это возможно, а если невозможно, выведите $$$-1$$$.

Пример
Входные данные
5
8
abcaacab
6
xyzxyz
4
abba
8
rprarlap
10
khyyhhyhky
Выходные данные
2
-1
0
3
2
Примечание

В первом наборе входных данных можно выбрать букву 'a' и удалить ее первое и последнее вхождение, получится строка 'bcaacb', являющаяся палиндромом. Также можно выбрать букву 'b' и удалить все ее вхождения, получится строка 'acaaca', также являющаяся палиндромом.

Во втором наборе входных данных можно показать, что нельзя выбрать букву и удалить какие-то ее вхождения так, чтобы получилась строка-палиндром.

В третьем наборе входных данных можно ничего не удалять, строка и так является палиндромом.