A palindrome is a string which reads the same backward and forward. Given a string S, compute how many operations are required to change it into a palindrome.

Allowed operations are:

• Insert a new character anywhere into the string
• Remove a single character
• Change a character into another

Input

The input contains string S. S consists of lowercase English letters.

Output

Output the smallest number of operations to change S into a palindrome.

Constraints

• 1 \le |S| \le 2000

Examples

Input:

saippuakauppas

Output:

1

Input:

aybabtu

Output:

2