Square Factors

In the ancient nation of Iwashiro, there was little rain this year, and the people were in trouble. That's why you, a new priest, have decided to perform a rain-making ceremony at Ryugasawa.

In the rain-making ceremony, you chant the prayer incantation written in the prayer book for the Dragon God to make it rain. When you finish the spell, the dragon god will ask you how many times the same word appears twice in a row in the spell. If you guess it, your prayer will be fulfilled and the Dragon God will send rain to you.

For example, if you cast the incantation ababababab, the six places in the incantation where the same word appears twice in a row are as follows.

• One place for abababab, starting with the first letter (abab appears twice in a row).
• Three places for abab, starting with the first, third, and fifth letters, respectively (ab appears twice in a row).
• Two baba places (ba appears twice in a row) starting with the second and fourth letters, respectively.

In order for your prayers to be fulfilled, you must answer the exact number of such passages when you cast any spell.

Given a string, create a program to find the number of places in the string where the same string appears twice in a row.

Input

The input is given in the following format.

$str$

A string $str$ consisting of English and lowercase letters is given on one line. However, the length of $str$ must be between 3 and 100,000.

Output

Output the number of times the same string appears twice in a given string on a single line.

Sample Input and Output

Sample Input 1

abababab

Sample Output 1

6

Sample Input 2

aaaaaaa

Sample Output 2

12

---