Dada una cadena ~S~ de longitud ~N~ donde ~S_{i}~ denota el carácter ~i~-ésimo de ~S~. Encuentre el número máximo de veces que se puede realizar la siguiente operación:

• Elija tres carácteres consecutivos en ~S~, ~ S_{i}~, ~S_{i+1}~, ~S_{i+2}~ ~(1 \leq i \leq |S|-2)~, tal que ~S_{i} = S_{i+1} \neq S_{i+2} ~, y reemplace ~S_{i+2}~ con ~S_{i}~.

Este problema no tendrá puntuación parcial.

Entrada

Una línea con una cadena ~S~. ~(3 \leq |S| \leq 200\,000)~. ~S~ consiste solo de letras minúsculas del alfabeto inglés.

Salida

Imprime el máximo número de veces que se puede realizar la operación.

Ejemplos

Entrada 1

accept

Salida 1

3

Podemos hacer la operación tres veces, de la siguiente manera:

• hazlo con ~i = 2~, cambiando la cadena a acccpt.
• hazlo con ~i = 3~, cambiando la cadena a acccct.
• hazlo con ~i = 4~, cambiando la cadena a accccc.

Entrada 2

atcoder

Salida 2

0

Entrada 3

anerroroccurred

Salida 3

16