Разделение строки называется палиндромным разбиением, если каждая подстрока является палиндромом. Например, “aba|b|bbabb|a|b|aba” — это палиндромное разбиение “ababbbabbababa”.

Определите наименьшее количество разрезов, необходимых для палиндромного разбиения данной строки. Например, для “ababbbabbababa” требуется минимум 3 разреза. Они имеют вид: “a|babbbab|b|ababa”. Если строка уже является палиндромом, то ответом будет 0 разрезов. Если все символы строки длины n разные, то требуется минимум n - 1 разрезов.

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

Одна строка s длины не более 1000.

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

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