You are given a string, consisting of lowercase English letters. In one operation, you are allowed to swap any two characters of the string .
A string anti-palindrome, if for every ( ). For example, the strings “codeforces”, “string” are anti-palindromes, but the strings “abacaba”, “abc”, “test” are not.of length is called an
Determine the minimum number of operations required to make the string anti-palindrome, or output , if this is not possible.an
The first line contains a single integer( ) — 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( ) — the length of the string .
The second line contains the string, consisting of lowercase English letters.
The sum ofover all test cases does not exceed .
For each test case, output a single integer — the minimum number of operations required to make the string anti-palindrome, or if this is not possible.an
In the first test case, the string “codeforces” is already an anti-palindrome, so the answer is .
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 .
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 .