题目描述

给定长度为 $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$ 变为完美回文的最少操作次数。

2
abcb
xxx

2
0

提示

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

对于第二组样例数据，xxx 已经是完美回文，因此无需任何操作。