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

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

Обмеження

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

Формат вхідних даних

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

Формат вихідних даних

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

Приклад вхідних даних

aebcbda

Приклад вихідних даних

2

Приклад вхідних даних

abbsa

Приклад вихідних даних

1