P14161 [ICPC 2022 Nanjing R] 完美回文

给定长度为 $n$ 的字符串 $S = s_0s_1\cdots s_{n-1}$，令 $f(S, d)$ 表示将 $S$ 左移 $d$ 次后获得的字符串。也就是说 $f(S, d) = s_{(d+0)\bmod n}s_{(d+1)\bmod n}\cdots s_{(d+n-1)\bmod n}$。称 $S$ 为完美回文，若对于$\textbf{所有}$非负整数 $d$，$f(S, d)$ 都是回文串。 给定长度为 $n$ 的仅由小写英文字母组成的字符串 $A = a_0a_1\cdots a_{n-1}$，您可以对 $A$ 进行任意次以下操作（包括零次）：选择整数 $i$ 满足 $0 \le i < n$ 并将 $a_i$ 改为任何小写英文字母。 求将 $A$ 变为完美回文的最少操作次数。 称长度为 $n$ 的字符串 $P = p_0p_1\cdots p_{n-1}$ 是回文串，若对于所有 $0 \le i < n$ 有 $p_i = p_{n-1-i}$。

有多组测试数据。第一行输入一个整数 $T$ 表示测试数据组数，对于每组测试数据： 第一行输入一个仅由小写英文字母构成的字符串 $a_0a_1\cdots a_{n-1}$（$1 \le n \le 10^5$）。 保证所有数据中字符串长度之和不超过 $10^6$。

每组数据输出一行一个整数表示将 $A$ 变为完美回文的最少操作次数。

对于第一组样例数据，可以将第一和第三个字符变为 `b`，这样字符串将变为 ``bbbb``。容易发现对于所有非负整数 $d$，$f(\text{``bbbb''}, d) = \text{``bbbb''}$ 且 ``bbbb`` 是回文串，因此 ``bbbb`` 是完美回文。这些变化需要消耗 $2$ 次操作，可以证明这是最少需要的操作次数。 对于第二组样例数据，``xxx`` 已经是完美回文，因此无需任何操作。