Minimum Operations to Palindrome

You are given a string s. Your task is to determine the minimum number of operations required to convert s into a palindrome.

An operation is defined as changing a single character at a particular position so that the string gradually approaches a palindrome. To achieve this, you can compare the characters in the string in pairs: the character at index i and the character at index n-i-1 (where n is the length of the string). For every pair that does not match, one operation is needed.

Formally, if you denote the string's characters as \(s_0, s_1, \ldots, s_{n-1}\), you only need to consider pairs \((s_i, s_{n-i-1})\) for \(0 \leq i < \frac{n}{2}\). The minimum number of operations required is equal to the number of indices \(i\) for which \(s_i \neq s_{n-i-1}\).

inputFormat

The first line contains a single integer T representing the number of test cases.

Each of the following T lines contains a non-empty string s consisting of lowercase letters.

outputFormat

For each test case, output a single integer on a new line that represents the minimum number of operations required to convert the string into a palindrome.

## sample

3
abca
aabb
abcba

1
2
0

</p>