Дано рядок ~S~, який містить малі англійські символи.

Ваше завдання — написати програму для видалення мінімальної кількості таких символів із рядка ~S~, щоб рядок став паліндромом. Порядок символів змінювати не дозволяється.

Обмеження

• ~1 \le |S| \le 10^3~, де ~|S|~ - довжина рядка
• ~S~ містить символи проміжку ['a'..'z']

Input

Вхідний потік містить рядок ~S~.

Output

У вихідний потік вивести відповідь - мінімальну кількість символів, які треба видалити з рядка ~S~ щоб утворився паліндром.

Sample Input 1

aebcbda

Sample Output 1

2

Sample Input 2

abbsa

Sample Output 2

1