K-Goodness String

Charles defines the goodness score of a string as the number of indices $i$ with $1 \le i \le N/2$ (1-indexed) such that $S_i \ne S_{N-i+1}$. For example, the string CABABC has a goodness score of 2 since $S_2 \ne S_5$ and $S_3 \ne S_4$.

Charles gave Ada a string $S$ of length $N$ consisting of uppercase letters and asked her to convert it into a string with a goodness score of $K$. In one operation, Ada can change any character in the string to any uppercase letter. Find the minimum number of operations required to transform the given string into a string with goodness score equal to $K$.

The first line of the input gives the number of test cases, $T$. $T$ test cases follow.

The first line of each test case contains two integers $N$ and $K$. The second line of each test case contains a string $S$ of length $N$, consisting of uppercase letters.

For each test case, output one line containing Case #x: y, where $x$ is the test case number (starting from 1) and $y$ is the minimum number of operations required to transform the given string $S$ into a string with goodness score equal to $K$.

• $1 \le T \le 100$.
• $0 \le K \le N/2$.

In sample case 1, the given string already has a goodness score of 1. Therefore the minimum number of operations required is 0.

In sample case 2, one option is to change the character at index 1 to B in order to have a goodness score of 2. Therefore, the minimum number of operations required is 1.