문자열을 앞에서부터 여러 개의 연속된 부분 문자열로 나누려고 한다.

나누어진 모든 부분 문자열은 앞에서 읽은 결과와 뒤에서 읽은 결과가 같은 팰린드롬이어야 한다.

알파벳 대문자로 이루어진 문자열 \(S\)가 주어졌을 때, 조건을 만족하도록 \(S\)를 나누어 얻을 수 있는 부분 문자열 개수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 문자열 \(S\)가 주어진다.

출력

\(S\)를 팰린드롬인 연속 부분 문자열들로 나누었을 때, 부분 문자열 개수의 최솟값을 출력한다.

제한 사항

• \(1 \le |S| \le 2,500\)
• \(S\)는 알파벳 대문자로만 이루어져 있다.

예제 입력 1

ABACDC

예제 출력 1

2

예제 설명 1

ABA와 CDC로 나누면 두 부분 문자열이 모두 팰린드롬이다. 하나의 부분 문자열로는 나눌 수 없으므로 최솟값은 2이다.

예제 입력 2

ABCBADEF

예제 출력 2

4

예제 설명 2

ABCBA, D, E, F로 나누면 모든 부분 문자열이 팰린드롬이며, 이보다 적은 개수로 나눌 수 없다.