One of your friends wants to write his own archiver. He is going to replace neighboring equal substrings with only one copy. For example, he is going to change substring "AA" with something like "2(A)" and if "A" is long enough it will reduce the file size.

But, before performing any coding stuff he wants to know how many such double substrings are there in the input file.

He asks you to help him, because this task is very difficult for him.

Input

Input file contains the text to be archived. It will only contain Latin letters (big and small). Its size will not exceed 200000 symbols. Letters are case sensitive, i.e. "X" is not equal to "x".

Output

Write a number of substrings of input text which can be written as "AA", i.e. consist of two equal concatenated parts.

Example

Input:
abcdefg

Output:
0

Input:
blabla

Output:
1

Input:
aCacaacaa

Output:
4