Harry got a string T, he wanted to know the number of T’s disjoint palindrome substring pairs. A string is considered to be palindrome if and only if it reads the same backward or forward. For two substrings of $T: \, x = T[a_1 \ldots b_1], \, y = T[a_2 \ldots b_2]$(where a1 is the beginning index of $x, b_1$ is the ending index of x. $a_2, b_2$ as the same of y), if both x and y are palindromes and $b_1 < a_2 \text{ or } b_2 < a_1$ then we consider (x, y) to be a disjoint palindrome substring pair of T.
There are several cases.
For each test case, there is a string T in the first line, which is composed by lowercase characters. The length of T is in the range of [1,100000].
For each test case, output one number in a line, indecates the answer.