J. Palindrome
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Recently, Student A has been studying strings. Certain peculiar strings caught his attention, so he named such strings "quasi-palindromic strings".

A string $$$s$$$ is a quasi-palindromic string if and only if the following two conditions are both satisfied:

1. There does not exist any contiguous substring $$$t$$$ of $$$s$$$ with length greater than or equal to 2 that is a palindromic string.

2. Suppose the length of $$$s$$$ is $$$n$$$, there exist $$$l,r$$$ satisfying $$$1\leq l\leq r\leq n$$$, such that after reversing the substring $$$s[l...r]$$$, $$$s$$$ becomes a palindromic string.

For example: The string "aac" is not a quasi-palindromic string because it contains the contiguous substring "aa" of length 2, which is a palindrome. The string "abdc" is not a quasi-palindromic string because there do not exist $$$l,r$$$ such that reversing the substring $$$s[l...r]$$$ would turn $$$s$$$ into a palindrome. The string "bcabca" is a quasi-palindromic string.

Now, given a string $$$T$$$, Student A wants to know how many contiguous substrings of $$$T$$$ are quasi-palindromic strings.

Here, contiguous substrings are distinguished solely by their starting and ending positions in the original string. For instance, in the string "aba", the contiguous substring [1,1] (the first "a") and the contiguous substring [3,3] (the last "a") are considered two different contiguous substrings, even though they are both the character "a".

Input

A string $$$T(1\leq |T|\leq 5\times 10^5)$$$.

Output

An integer representing the number of contiguous substrings of $$$T$$$ that are quasi-palindromic strings.

Examples
Input
abcabc
Output
9
Input
abc
Output
3
Note

In the first sample, all contiguous substrings of length 1 are quasi-palindromic strings. Among substrings longer than 1, the quasi-palindromic strings are "abcab", "bcabc", and "abcabc".