Palinilap

팰린드롬은 앞에서 읽어도 뒤에서 읽어도 같은 단어다. 예를 들어 a, abba, anavolimilovana는 팰린드롬이다.

표본은 영어 소문자로만 이루어진 길이 1 이상의 문자열이고, 표본의 가중치는 그 부분문자열 중 팰린드롬인 것의 개수다. 같은 단어가 여러 위치에 나타나면 나타난 횟수만큼 따로 센다.

정확히 말하면, 길이가 $n$인 표본을 $w$라고 하자. 단어 $w_{a,b}$는 $w$의 $a$번째 위치부터 $b$번째 위치까지의 문자를 모두 모은 것이다. $w$의 가중치는 $w_{a,b}$가 팰린드롬이 되는 정수 쌍 $(a, b)$ ($1 \le a \le b \le n$)의 개수로 정의한다.

표본 $w$가 주어진다. $w$를 그대로 두어도 되고, 위치 하나를 골라 그 위치의 글자를 원하는 글자로 바꿔도 된다. 이렇게 해서 얻을 수 있는 가중치의 최댓값을 구하라.

첫째 줄에 표본 $w$가 주어진다. $w$는 영어 소문자로만 이루어져 있고, 길이는 1 이상 1000 이하다.

얻을 수 있는 가중치의 최댓값을 출력한다.

입력이 aaaa이면 모든 부분문자열이 이미 팰린드롬이므로 그대로 두는 것이 최적이다.

입력이 baccb이면 두 번째 글자를 c로 바꿔 bcccb를 만들 수 있고, 이때 가중치는 9다.