## Anti Palindrome solution codechef

A string $T$ is called **semi-palindrome** if you can rearrange the characters of $T$ to make it into a palindrome.

For eg. if $T=aabb$, it isn’t a palindrome as of now, but it can be rearranged to form $abba$, which is a palindrome. Thus, $T=aabb$ is a semi-palindrome.

An **anti-palindrome** is the opposite of a semi-palindrome. In particular, a string $T$ is called an anti-palindrome if it is not possible to rearrange the characters of $T$ to make it into a palindrome.

For eg. if $T=abc$, there is no rearrangement of this string which makes it into a palindrome. Hence, $T=abc$ is an anti-palindrome.

Now on to the problem:

You are given a string $S=S_{1}S_{2}…S_{N}$ consisting of $N$ english lowercase letters.

Your aim is to convert $S$ into an anti-palindrome. For this, you are allowed to do the following operation as many times as you want (even 0 times) :

- Select an index $i$ $(1≤i≤N)$ and change $S_{i}$ to any other english lowercase letter.

Find the minimum number of operations needed to make $S$ into an anti-palindrome.

**Note:** It can be proven that for the given constraints ($2≤N≤1_{5}$), it is always possible to make $S$ into an anti-palindrome using the operations.

## Anti Palindrome solution codechef

- The first line of input will contain a single integer $C$, denoting the number of test cases.
- Each test case consists of two lines of input.
- The first line of each test case contains an integer $N$ — the length of the string $S$.
- The next line contains the string $S$ of length $N$.

### Output Format

For each test case, output the minimum number of operations needed to make $S$ into an anti-palindrome.

### Constraints

- $1≤C≤5⋅1_{5}$
- $2≤N≤1_{5}$
- $S$ contains only english lowercase letters.
- The sum of $N$ over all testcases won’t exceed $1_{5}$.

### Sample 1:

Input

Output

5 2 ab 2 aa 3 abc 3 aaa 3 abb

0 1 0 2 1

### Explanation:

**Testcase 1:** The given string $ab$ is already an anti-palindrome, since there is no way to rearrange the letters to make it into a palindrome. So, we don’t need to do any operations on it to make it an anti-palindrome. Hence the answer is $0$.

**Testcase 2:** The given string $aa$ is a palindrome, and so it is not an anti-palindrome. We can change it to $ab$ using $1$ operation, and it becomes an anti-palindrome. Hence the answer is $1$.

**Testcase 3:** The given string $abc$ is already an anti-palindrome, since there is no way to rearrange the letters to make it into a palindrome. So, we don’t need to do any operations on it to make it an anti-palindrome. Hence the answer is $0$.

**Testcase 4:** The given string $aaa$ is a palindrome, and so it is not an anti-palindrome. We can change it to $abc$ using $2$ operations, and it becomes an anti-palindrome. There is no way to make it into an anti-palindrome using only 1 operation. Hence the answer is $2$.

**Testcase 5:** The given string $abb$ is a semi-palindrome, since it can be rearranged to form $bab$ which is a palindrome. So $abb$ is not an anti-palindrome. We can change it to $abc$ using $1$ operation, and it becomes an anti-palindrome. Hence the answer is $1$.