Palindrome is a word that reads in both directions equally. Write a program that turns any word into a palindrome, erasing the minimum number of letters from it. In a word, we will consider the sequence of lowercase letters of the Latin alphabet.

Input

In a single line there is one word - a sequence of small Latin letters with no spaces (no more than 255 symbols).

Output

Print one number - the minimum number of characters to be deleted, so that the word becomes a palindrome.