Розбиття на паліндроми

Розбиття рядка називається паліндромним розбиттям, якщо кожна його підрядок є паліндромом. Наприклад, "aba|b|bbabb|a|b|aba" є паліндромним розбиттям рядка "ababbbabbababa".

Вам потрібно визначити найменшу кількість розрізів, необхідних для паліндромного розбиття заданого рядка. Наприклад, для рядка "$ababbbabbababa$" потрібно щонайменше $3$ розрізи, які можуть бути такими: "$a|babbbab|b|ababa$". Якщо рядок вже є паліндромом, то відповідь — $0$ розрізів. Якщо всі символи рядка довжини $n$ різні, то потрібно щонайменше $n-1$ розрізів.

Вхідні дані

Один рядок $s$ довжиною не більше $1000$ символів.

Вихідні дані

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

Приклади