Minimum Replacements to Palindrome

Given a string \( s \), your task is to compute the minimum number of character replacements required to transform \( s \) into a palindrome. A palindrome is a string that reads the same forwards and backwards. Formally, for a string \( s \) of length \( n \), you need to count the number of indices \( i \) (where \( 0 \le i < \frac{n}{2} \)) such that \( s[i] \neq s[n-i-1] \).

Example:

• For \( s = \texttt{abba} \), no replacements are needed because it is already a palindrome.
• For \( s = \texttt{abbaa} \), one replacement is required.
• For \( s = \texttt{abcdef} \), three replacements are required.

You need to process multiple test cases. The input format is described below.

inputFormat

The first line of input contains an integer \( T \) representing the number of test cases. Each of the following \( T \) lines contains a string \( s \).

\( \textbf{Constraints:} \) \( 1 \le T \le 1000 \) and each string \( s \) consists of lowercase English letters.

outputFormat

For each test case, output a single line containing an integer representing the minimum number of replacements needed to convert the string into a palindrome.

## sample

6
abba
abbaa
aabbb
a
aa
abcdef

0
1
2
0
0
3

</p>