You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

给定长度为 $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$ 为完美回文串。

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

Format

Input

本题有多组数据。

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

输入一行一个字符串表示青蛙哥拿到的字符串 $S$。

Output

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

Samples

样例输入

2
abcb
xxx

样例输出

2
0

Limitation

对于 $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$，字符串中只包含小写字母。