Minimum Operations to Convert String into Palindrome

You are given a string s. In one operation, you can change a character of the string to any other character. Your task is to determine the minimum number of operations required such that the string becomes a palindrome.

A palindrome is a string that reads the same backward as forward. Mathematically, for a string \(s\) of length \(n\), the condition for being a palindrome is:

\[ s_i = s_{n-i+1} \quad \text{for all } 1 \leq i \leq n \]

You will be given multiple queries. For each query, calculate the required number of operations.

inputFormat

The first line contains an integer q denoting the number of queries.

Each of the next q lines contains a string s.

Constraints:

• The string s consists of only lowercase English letters.
• The length of s can be up to 10⁵ (in a single query).

outputFormat

For each query, output a single integer representing the minimum number of operations required to convert the string into a palindrome. Each result should be printed on a new line.

## sample

4
abcd
racecar
abccbx
abcba

2
0
1
0

</p>