← 返回题目列表

Codeforces · 1822/E

E. 制作反回文

中文机器翻译题面 查看原题

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

长度为 $$$n$$$ 的字符串 $$$s$$$ 称为反回文,如果 $$$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$$$小写英文字母组成。

所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数 - 使字符串 $$$s$$$ 成为反回文所需的最少操作数,如果不可能,则输出 $$$-1$$$。

示例

输入 #1

10
10
codeforces
3
abc
10
taarrrataa
10
dcbdbdcccc
4
wwww
12
cabbaccabaac
10
aadaaaaddc
14
aacdaaaacadcdc
6
abccba
12
dcbcaebacccd

输出 #1

0
-1
1
1
-1
3
-1
2
2
2

注意

在第一个测试用例中,字符串“codeforces”已经是反回文,所以答案是$$$0$$$。

在第二个测试用例中,可以看出字符串“abc”无法通过执行允许的操作转换为反回文,因此答案为$$$-1$$$。

在第三个测试用例中,交换字符串“taarrrataa”的第二个和第五个字符就足够了,新字符串“trararataa”将是反回文,所以答案是$$$1$$$。