Problem statement

Given a string, $S$, of length $$ consisting of lowercase characters, in one action, you have to change any character to any other character.

Find the minimum number of actions required so that the resulting string is a palindrome.

Input format

The single line of input contains the string $S$ of length $N(1 \leq N \leq 10^6)$.

Output format

Print a single integer, the minimum number of actions required.

---

Sample

Input

madam

Output

0

Input

radecar

Output

1

---

Explanation

Sample $1$: is already a palindrome, so $0$ action is needed.

Sample $2$: We can change d to c to get racecar using 1 action.

---

Solution

For a palindrome, the first character is the same as the last character. Similarly, the second character is the same as the second to last character.

We can iterate using two pointers.

1. Starting at the first character moving to the right
2. Starting at the last character moving to the left At each step
3. If the characters match, nothing needs to be done.
4. If the characters don’t match, we can make the characters the same using one action.

Since we are iterating over the string once, the time complexity is $O(N)$.