Редактор работает со словом и хочет превратить его в палиндром — слово, которое читается одинаково слева направо и справа налево.

За одну операцию он может вставить один символ в любую позицию слова: в начало, в конец или между любыми двумя соседними символами.

Требуется определить минимальное количество символов, которые нужно добавить, чтобы исходное слово стало палиндромом.

Входные данные

В единственной строке задано непустое слово из строчных латинских букв длиной до 1000.

Выходные данные

Выведите одно целое число — минимальное количество вставок, необходимых, чтобы слово стало палиндромом.

Ограничения

• 1 <= |s| <= 1000
• строка состоит только из строчных латинских букв

Примеры

Пример 1

Входные данные

mbadm

Выходные данные

2

Пояснение

Наибольшая палиндромная подпоследовательность 'mam' (или 'mdm') имеет длину 3, поэтому нужно вставить 5 - 3 = 2 символа.

Пример 2

Входные данные

a

Выходные данные

0

Пример 3

Входные данные

ab

Выходные данные

1