Hide

Problem M
Alchemy

You just finished day one of your alchemy class! For your alchemy homework, you have been given a string of lowercase letters and wish to make it a palindrome. You’re only a beginner at alchemy though, so your powers are limited. In a single operation, you may choose exactly two adjacent letters and change each of them into a different lowercase letter. The resulting characters may be the same as or different from one another, so long as they were both changed by the operation.

Formally, if the string before the operation is $s$ and you chose to change characters $s_ i$ and $s_{i+1}$ to produce string $t$, then $s_ i \neq t_ i$ and $s_{i+1} \neq t_{i+1}$ must be true, but $t_ i = t_{i+1}$ is permitted.

Compute the minimum number of operations needed to make the string a palindrome.

Input

The single line of input contains a string of $n$ $(2 \le n \le 100)$ lowercase letters, the string you are converting into a palindrome.

Output

Output a single integer, which is the minimum number of operations needed to make the string a palindrome.

Sample Input 1 Sample Output 1
ioi
0
Sample Input 2 Sample Output 2
noi
1
Sample Input 3 Sample Output 3
ctsc
1
Sample Input 4 Sample Output 4
fool
2
Sample Input 5 Sample Output 5
vetted
2

Please log in to submit a solution to this problem

Log in