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 substrings S（i...j ）satisfies j-i+1 is odd then Si+k）=S（j-k） for k = 0,1,...,j-i+1.

The first line contains integer T(1≤T≤100) representing the number of test case.
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≤|s|≤100.

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

3
ncncn
aaaaba
aaaabb

0
1
2