Наборщик работает с полосой текста, представленной строкой s. Ему нужно разрезать эту строку на несколько подряд идущих кусков так, чтобы каждый получившийся кусок читался одинаково слева направо и справа налево, то есть был палиндромом.

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

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

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

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

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

Ограничения

1 <= |s| <= 2000

Примеры

Пример 1

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

a

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

0

Пример 2

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

ab

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

1