Super-palindrome

比赛题目可以自行下载：http://acm.hdu.edu.cn/downloads/CCPC2018-Hangzhou-ProblemSet.pdf

You are given a string that is consisted of lowercase English alphabet. You are supposed to change it into a super-palindrome string in minimum steps. You can change one character in string to another letter per step.

A string is called a super-palindrome string if all its substrings with an odd length are palindrome strings. That is, for a string s, if its substring $s_{i\cdots j} $ satisfies $ j-i+1 $ is odd then $s_{i+k}=s_{j-k} $ for $ k = 0 , 1 , \cdots j-i+1 $.

The first line contains an integer $ T\left( 1 \leq T \leq 100 \right) $ representing the number of test cases.

For each test case, the only line contains a string, which consists of only lowercase letters. It is guaranteed that the length of string satisfies $ 1 \leq \vert s \vert \leq 100 .$

For each test case, print one line with an integer refers to the minimum steps to take.

3
ncncn
aaaaba
aaaabb

0
1
2

For second test case aaaaba, just change letter b to a in one step.

2017中国大学生程序设计竞赛-杭州站-重现赛（感谢浙江理工）