CF2267A.Turn Into a Palindrome

Ali has a string $s$ consisting of $n$ lowercase Latin letters. He also has a character $c$, which is a lowercase Latin letter. In one coin, he can perform the following operation on the string $s$:

• First, he chooses an index $1\le i\le n$.
• Then he replaces $s_i$ with the character $c$.

Ali wants to turn the string $s$ into a palindrome$^{\text{∗}}$, but he does not want to spend too many coins on it. Your task — compute the minimum number of coins he has to spend to turn the string $s$ into a palindrome.

$^{\text{∗}}$A string $t$ of length $m$ is a palindrome if $t_i = t_{m-i+1}$ holds for every $1\le i\le m$

阿里有一个由 $n$ 个小写拉丁字母组成的字符串 $s$，以及一个字符 $c$（也是一个小写拉丁字母）。他每次花费一枚硬币，可以对字符串 $s$ 执行如下操作：

• 首先，他选择一个下标 $1\le i\le n$；
• 然后，他将 $s_i$ 替换为字符 $c$。

阿里希望将字符串 $s$ 变成一个回文串$^{\text{∗}}$，但又不想花费过多的硬币。你的任务是：计算出将字符串 $s$ 变为回文串所需的最少硬币数。

$^{\text{∗}}$ 一个长度为 $m$ 的字符串 $t$ 是回文串，当且仅当对每个 $1\le i\le m$，均有 $t_i = t_{m-i+1}$ 成立。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 500$). The description of the test cases follows.

The first line of each test case contains an integer $n$ and a lowercase Latin letter $c$ ($1\le n\le 100$) — the length of the string $s$ and the character $c$.

The second line of each test case contains the string $s$ consisting of $n$ lowercase Latin letters.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 500$）。随后是测试用例的描述。

每个测试用例的第一行包含一个整数 $n$ 和一个小写拉丁字母 $c$（$1\le n\le 100$）——分别表示字符串 $s$ 的长度和字符 $c$。

每个测试用例的第二行包含字符串 $s$，该字符串由 $n$ 个小写拉丁字母组成。

For each test case, output one number — the minimum number of coins Ali needs to spend for the string to become a palindrome.

对于每个测试用例，输出一个数字——Ali 为使该字符串变为回文串所需花费的最少硬币数。

In the first test case, in one coin, you can replace $s_3$ with $\texttt{b}$. After the replacement, the string becomes $\texttt{abba}$, which is already a palindrome. It can be proven that $1$ is the minimum number of coins required.

In the second test case, the string $s$ is already a palindrome.

In the third test case, it is enough to change $s_1$ and $s_5$ to $\texttt{e}$. After two replacements, the string becomes $\texttt{ebcbe}$, which is already a palindrome.

In the fourth test case, in two coins, you can replace $s_1$ and $s_7$.

在第一个测试用例中，花费一枚硬币即可将 $s_3$ 替换为 $\texttt{b}$。替换后，字符串变为 $\texttt{abba}$，它本身已是一个回文串。可以证明，所需的最少硬币数量为 $1$。

在第二个测试用例中，字符串 $s$ 本身已是一个回文串。

在第三个测试用例中，只需将 $s_1$ 和 $s_5$ 均改为 $\texttt{e}$。经过两次替换后，字符串变为 $\texttt{ebcbe}$，它本身已是一个回文串。

在第四个测试用例中，花费两枚硬币即可替换 $s_1$ 和 $s_7$。