说明

给定长度为 $n$ 的字符串 $S$ ，令 $f(S,d)$ 表示将 $S$ 中前 $d$ 个字符截取后按原顺序放到 $S$ 末尾，所得到的字符串。

如假设 $S$ 为abcde，则 $f(S,0)$ 为abcde，$f(S,1)$ 为bcdea，$f(S,2)$ 为cdeab，$f(S,3)$ 为deabc，$f(S,4)$ 为eabcd。

回文串指顺读和倒读都一样的字符串。

若对于所有在 $[0,n-1]$ 内的 $d$ ，$f(S,d)$ 都是回文串，则称 $S$ 为完美回文串。

小 L 拿到了一个字符串 $S$，每次操作小 L 可以指定字符串中的一个位置，将其修改为任意一个字母，求将 $S$ 变成完美回文串的最少操作次数。

输入格式

本题有多组数据。

第一行一个正整数 $T$ 表示数据组数，对于每组数据：

输入一行一个字符串表示小 L 拿到的字符串 $S$。

输出格式

对于每组数据，输出一行一个整数，表示最少操作次数。

样例

2
abcb
xxx

2
0

提示

数据范围

对于 $20\%$ 的数据，$1\le n\le 10$ 。

对于另外 $30\%$ 的数据，$1\le n\le 1000$，字符串中只包含a和b两个字母。

对于 $100\%$ 的数据，$1\le n\le 10^5,1\le T\le 10$，字符串中只包含小写字母。