题目描述

给定一个由小写英文字母组成的字符串 $s$。在一次操作中，你可以交换字符串 $s$ 中任意两个字符。

如一个长度为 $n$ 的字符串 $s$ 满足对于每个 $i(1≤i≤n)$，都有 $s[i]≠s[n-i+1]$，那么它被称为反回文字符串。例如，字符串 codeforces 和 string 是反回文字符串，但字符串 abacaba、abc、test 不是。

请确定使字符串 $s$ 成为反回文字符串所需的最小操作次数，如果无法实现，则输出 -1。

输入格式

第一行包含一个整数 $t(1≤t≤10^4)$——测试用例的数量。接下来是 $t$ 组测试用例，每个测试用例占两行。第一行包含一个整数 $n(1≤n≤2⋅10^5)$，表示字符串 $s$ 的长度。第二行包含长度为 $n$ 的字符串 $s$，由小写英文字母组成。

所有测试用例中 $n$ 的总和不超过 $2⋅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。