В архиве хранится кодовая последовательность s, состоящая из строчных латинских букв. Требуется превратить её в симметричную последовательность, которая читается одинаково слева направо и справа налево.

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

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

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

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

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

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

Ограничения

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

Примеры

Пример 1

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

a

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

0

Пример 2

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

ab

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

1