Description

小Q最近在研究一些字符串，最近他发现了有一种字符串是超级字符串。 超级字符串是这样子定义的： 对于一个字符串 $L$，它的任意一个长度为奇数的子串都是回文字符串，那么称字符串 $L$ 为超级字符串。 现在小Q得到了一些字符串 $L$ ，他想知道把 $L$ 变成超级字符串最少需要修改多少个字母。

Input Format

第一行一个整数 $T$ ，表示字符串的数量 接下来 $T$ 行，每行一个字符串 $L$ ，即题目中表述的字符串

Output Format

共 $T$ 行，每行一个整数，表示把对应的字符串变成超级字符串所需要修改的最少字母数。

Sample

样例输入

3
ncncn
aaaaba
aaaabb

样例输出

0
1
2

样例解释

对于第二个样例aaaaba，只需要把其中的字母b变成字母a就可以了。

Hint

对于 $30\%$ 的数据，$1 \le |L| \le 5$

对于 $60\%$ 的数据，$1 \le |L| \le 20$

对于 $100\%$ 的数据，$1 \le |L| \le 100$ ， $1 \le T \le 100$