Cat and string of characters

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

When Marichka is not around, Zenik gets sad. In such cases, to cheer up, he plays a game with his cat.

Zenik writes a certain sequence of uppercase Latin letters \(s\) on a sheet of paper. And then the following happens.

If the cat sees two identical letters in a row anywhere — it meows.

After that, Zenik inserts any letter anywhere in the string.

The process repeats until there are two identical letters in a row in the string. When everything ends — the cat goes to sleep in the kitchen.

Can you calculate the minimum number of times the cat will meow before going to sleep in the kitchen?

Input

The single line contains the string \(s\).

Output

In the single line output an integer — the minimum number of times the cat says: "Meow!".

Constraints

\(1 \le |s| \le 10^3\),

all characters in \(s\) are uppercase Latin letters.

Samples