Palinilap

A palindrome is a word that reads the same forwards and backwards. For example, a, abba and anavolimilovana are palindromes.

A sample is a string of one or more lower case letters of the English alphabet. The weight of a sample is the number of its substrings that are palindromes, and a word that appears at several positions is counted once per occurrence.

More precisely, let $w$ be a sample of length $n$. The word $w_{a,b}$ consists of all characters from position $a$ to position $b$ of $w$. The weight of $w$ is the number of pairs of integers $(a, b)$ with $1 \le a \le b \le n$ such that $w_{a,b}$ is a palindrome.

You are given the sample $w$. You may leave it unchanged, or you may pick exactly one position and change the letter at that position to any letter. Find the largest weight you can obtain this way.

The first line contains the sample $w$. It consists of lower case letters of the English alphabet only, and its length is between 1 and 1000.

Print the largest weight you can obtain.

For the input aaaa, every substring is already a palindrome, so it is best left unchanged.

For the input baccb, changing the second letter to c gives bcccb, whose weight is 9.