Minimal Moves to Almost Palindrome

You are given a number of test cases. In each test case, you are given a string. Your task is to determine the minimal number of moves required to make the string an "almost palindrome".

A string is considered an almost palindrome if you can make it a palindrome by changing the minimum number of characters. In one move, you can change a character in the string so that a mismatched pair (i.e. characters at positions i and n-i-1, where n is the length of the string) becomes identical. The minimal number of moves required is simply the count of mismatched character pairs when comparing the string with its reverse.

For example, for the string "abca", you can change the second character 'b' to 'c' (or the third character 'c' to 'b') to obtain the palindrome "acca" or "abba". Thus, the answer is 1 move.

inputFormat

The input begins with an integer T (T ≥ 1) on a single line, representing the number of test cases. Each of the following T lines contains a non-empty string whose minimal moves to become an almost palindrome is to be determined.

You should read from stdin.

outputFormat

For each test case, output a single integer on a new line, which is the minimal number of moves required to make the corresponding string an almost palindrome.

You should write to stdout.

## sample

1
abca

1

</p>