Description

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[a1…b1],y=T[a2…b2](where a1 is the beginning index of x,b1 is the ending index of x. a2,b2 as the same of y), if both x and y are palindromes and b1<a2 or b2<a1 then we consider (x, y) to be a disjoint palindrome substring pair of T.

在一个S串中找两个回文串，两个回文串没有重叠的部分。问有多少个这样的回文串对。

Hint

For the first test case there are 4 palindrome substrings of T.

They are: S1=T[0,0] S2=T[0,2] S3=T[1,1] S4=T[2,2] And there are 3 disjoint palindrome substring pairs.

They are: (S1,S3) (S1,S4) (S3,S4). So the answer is 3.

Format

Input

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].

Output

For each test case, output one number in a line, indecates the answer.

Samples

aca 
aaaa

3 
15