Minimum Changes to Palindrome

Given a string s, determine the minimum number of character changes required to transform it into a palindrome. A string is a palindrome if it reads the same forwards and backwards. Formally, for a string of length n, you need to ensure that for all indices \( i \) where \( 0 \le i < \lfloor n/2 \rfloor \), the equality \( s[i] = s[n-i-1] \) holds. If \( s[i] \neq s[n-i-1] \), a change is needed. The total number of such changes is the sum of modifications required for all index pairs.

You are given multiple queries. For each query, output the minimum number of changes required for the input string.

inputFormat

The first line contains an integer T (\(1 \le T \le 10^5\)) representing the number of queries. Each of the following T lines contains a non-empty string s consisting of lowercase English letters. The length of each string is at most \(10^5\) characters.

outputFormat

For each query, output a single line with an integer representing the minimum number of changes needed to make the corresponding string a palindrome.

3
aabb
racecar
abcd

2
0
2