팰린드롬 분할

팰린드롬은 앞에서 읽어도 뒤에서 읽어도 같은 단어이다. aba나 a는 팰린드롬이고, abaccbcb나 anavolimilana는 팰린드롬이 아니다.

어떤 단어가 팰린드롬이 아니어도, 여러 개의 팰린드롬 부분 문자열로 나눌 수 있다. 단어가 주어졌을 때 모든 조각이 팰린드롬이 되도록 나누되, 조각의 개수를 최소로 만들려고 한다.

예를 들어 abaccbcb는 aba, cc, bcb의 세 조각으로 나누면 모두 팰린드롬이 된다. 두 조각만으로는 모든 조각을 팰린드롬으로 만들 수 없으므로 답은 3이다. 마찬가지로 anavolimilana는 ana, v, o, limil, ana의 다섯 조각으로 나눌 수 있으므로 답은 5이다.

주어진 문자열을 최소 개수의 팰린드롬 부분 문자열로 나누었을 때 필요한 조각 수를 출력하는 프로그램을 작성하라. 문자열 전체가 이미 팰린드롬이라면 나누지 않아도 된다.

첫째 줄에 단어가 주어진다. 단어는 영어 소문자로만 이루어져 있으며, 길이는 2,000을 넘지 않는다.

주어진 문자열을 최소 개수의 팰린드롬 부분 문자열로 나누었을 때의 조각 수를 출력한다.