CF2267A Turn Into a Palindrome

Ali 有一个由 $n$ 个小写拉丁字母组成的字符串 $s$。他还有一个字符 $c$，也是一个小写拉丁字母。每花费一枚硬币，他可以对该字符串 $s$ 执行以下操作： - 首先，他选择一个下标 $1\le i\le n$。 - 然后他将 $s_i$ 替换为字符 $c$。 Ali 想把字符串 $s$ 变成一个回文串$^{\text{∗}}$，但他不想花太多硬币。你的任务是计算他要把字符串 $s$ 变成回文串所需花费的最少硬币数。 $^{\text{∗}}$ 长度为 $m$ 的字符串 $t$ 是回文串，当且仅当对于每个 $1\le i\le m$ 都有 $t_i = t_{m-i+1}$。

每个测试包含多个测试用例。第一行包含测试用例数 $t$（$1 \le t \le 500$）。接下来是各测试用例的描述。 每个测试用例的第一行包含一个整数 $n$ 和一个小写拉丁字母 $c$（$1\le n\le 100$）——字符串 $s$ 的长度和字符 $c$。 每个测试用例的第二行包含由 $n$ 个小写拉丁字母组成的字符串 $s$。

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

在第一个测试用例中，花费一枚硬币，你可以将 $s_3$ 替换为 $\texttt{b}$。替换后，字符串变为 $\texttt{abba}$，它已经是回文串了。可以证明所需的最少硬币数为 $1$。 在第二个测试用例中，字符串 $s$ 已经是回文串。 在第三个测试用例中，只需将 $s_1$ 和 $s_5$ 改为 $\texttt{e}$。经过两次替换后，字符串变为 $\texttt{ebcbe}$，它已经是回文串了。 在第四个测试用例中，花费两枚硬币，你可以替换 $s_1$ 和 $s_7$。