E. Делаем антипалиндромы
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана строка $$$s$$$, состоящая из строчных букв латинского алфавита. За одну операцию вы можете поменять местами любые два символа в строке $$$s$$$.

Строка $$$s$$$ длины $$$n$$$ называется антипалиндромом, если $$$s[i] \ne s[n - i + 1]$$$ для каждого $$$i$$$ ($$$1 \le i \le n$$$). Например, строки «codeforces», «string» являются антипалиндромами, а строки «abacaba», «abc», «test» — не являются.

Определите минимальное число операций, необходимое, чтобы сделать из строки $$$s$$$ антипалиндром, или выведите $$$-1$$$, если это невозможно.

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

В первой строке находится единственное целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следуют описания наборов входных данных.

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

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

Cумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

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

Пример
Входные данные
10
10
codeforces
3
abc
10
taarrrataa
10
dcbdbdcccc
4
wwww
12
cabbaccabaac
10
aadaaaaddc
14
aacdaaaacadcdc
6
abccba
12
dcbcaebacccd
Выходные данные
0
-1
1
1
-1
3
-1
2
2
2
Примечание

В первом примере строка «codeforces» изначально является антипалиндромом, поэтому ответом является $$$0$$$.

Во втором примере можно показать, что строку «abc» нельзя сделать антипалиндромом с помощью таких операций, поэтому ответом является $$$-1$$$.

В третьем примере в строке «taarrrataa» достаточно переставить местами второй и пятый символы, и новая строка «trararataa» будет антипалиндромом, поэтому ответом является $$$1$$$.