팰린드롬 분할

주어진 문자열을 여러 개의 팰린드롬 부분 문자열로 나누려고 한다. 예를 들어 ABACABA는 {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}처럼 나눌 수 있다.

문자열 전체를 팰린드롬 조각들로 나눌 때 필요한 조각 수의 최솟값을 구하라.

첫째 줄에 알파벳 대문자로만 이루어진 문자열이 주어진다. 문자열의 길이는 최대 2,500이다.

첫째 줄에 팰린드롬 분할에 필요한 조각 수의 최솟값을 출력한다.