A palindrome is a word that reads the same backwards as forwards. For example, a, abba, and anavolimilovana are palindromes. A sample is a string of one or more lowercase letters of the English alphabet, and the weight of a sample is the number of its substrings (words) that are palindromes, counting each word occurrence separately.

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

You are given the sample $w$. It can either be left unchanged, or exactly one position can be chosen and the letter on that position arbitrarily changed. Find the maximal possible sample weight that can be obtained as described above.

Input Specification

The first line of input contains the given sample $w$ – a string of lowercase letters of the English alphabet.

Output Specification

You must output the required maximal possible weight.

Constraints

Let $n$ be the length of the given sample.

Subtask	Score	Constraints
$1$	$17$	$1\le n\le 100$
$2$	$37$	$101\le n\le 5000$
$3$	$46$	$5001\le n\le 100000$

Sample Input 1

aaaa

Sample Output 1

10

Explanation for Sample Output 1

Each substring from the sample already is a palindrome, so it is best left unchanged.

Sample Input 2

baccb

Sample Output 2

9

Explanation for Sample Output 2

If we change the second letter of the sample to c, we will get the sample bcccb with a weight of $9$.

Sample Input 3

slavko

Sample Output 3

7