Minimum Operations to Palindrome

You are given a string s. In one operation, you can choose any two characters that are in symmetrical positions (i.e. the character at position i and the character at position n-i+1) and if they are different, you can change one of them so that they match. Your task is to determine the minimum number of operations required to turn the string into a palindrome.

Formally, for a string s of length n, you need to compute the value:

\[ \text{ops}(s)=\sum_{i=1}^{\lfloor n/2\rfloor} \mathbf{1}_{\{s_i \neq s_{n-i+1}\}}, \]

where \(\mathbf{1}_{\{condition\}}\) is an indicator function that is 1 when the condition is true, and 0 otherwise.

Note: The positions in the string are considered using 1-indexing in the formula above, but the implementation can use 0-indexing as convenient.

inputFormat

The input begins with a single integer t (1 ≤ t ≤ 10⁴) representing the number of test cases. Each of the following t lines contains a non-empty string s consisting of lowercase English letters. The length of each string will be at most 10⁴.

outputFormat

For each test case, print a single integer on a new line representing the minimum number of operations required to transform the given string into a palindrome.

## sample

1
 a

0

</p>