给你一个字符串$$$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$$$。