Jon talks with his friend Denny and their conversation is interesting. They say a word alternatively. A word have all equal letter.Jon says first word. They understand each other perfect and even write all words in a string without spaces one after another. Total number of words said by both friends are not mare than 5000.

But now you want to know meaning of this conversation. For that you want to know how many substrings of given string(conversation) are "Key string" .

String is called Key string if one can make it palindrome by doing following operation on string any number of time.

operation: Replace a character with a string which has length two and both character of that string should be same as replaced character.For example you can replace 'a' with "aa" but not "bb".

For example, "aabaaa","aabcccbba","aa" are key strings and "abc" is not.

Your task is to count the number of key substring of a given string.

Input Format

First and only line contains a string which contains all word said by jon and denny (without spaces). Length of string is not more than 1000000.

Output Format

Print number of key substring of given string.

Setter: Sagar Savaliya