310365: CF1822E. Making Anti-Palindromes

E. Making Anti-Palindromestime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

You are given a string $s$, consisting of lowercase English letters. In one operation, you are allowed to swap any two characters of the string $s$.

A string $s$ of length $n$ is called an anti-palindrome, if $s[i] \ne s[n - i + 1]$ for every $i$ ($1 \le i \le n$). For example, the strings "codeforces", "string" are anti-palindromes, but the strings "abacaba", "abc", "test" are not.

Determine the minimum number of operations required to make the string $s$ an anti-palindrome, or output $-1$, if this is not possible.

Input

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of the test cases follows.

Each test case consists of two lines. The first line contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the length of the string $s$.

The second line contains the string $s$, consisting of $n$ lowercase English letters.

The sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case, output a single integer — the minimum number of operations required to make the string $s$ an anti-palindrome, or $-1$ if this is not possible.

ExampleInput

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

Output

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

Note

In the first test case, the string "codeforces" is already an anti-palindrome, so the answer is $0$.

In the second test case, it can be shown that the string "abc" cannot be transformed into an anti-palindrome by performing the allowed operations, so the answer is $-1$.

In the third test case, it is enough to swap the second and the fifth characters of the string "taarrrataa", and the new string "trararataa" will be an anti-palindrome, so the answer is $1$.

题目大意：
给定一个由小写英文字母组成的字符串 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）——测试用例的数量。
- 每个测试用例包含两行：
- 第一行包含一个整数 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
```题目大意： 给定一个由小写英文字母组成的字符串 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）——测试用例的数量。 - 每个测试用例包含两行： - 第一行包含一个整数 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 ```