题目描述

小红有一个字符串 s，只包含小写字母。如果一个字符串中，不包含连续的三个相同的字母，并且不存在两个相同的字母紧挨着两个相同的字母，那么这个字符串就是合法的。例如，字符串“aaa”是不合法的，字符串"aabb"也是不合法的。字符串”aab”是合法的。

小红想知道，最少需要删除多少个字符，才能使得字符串变成合法的。

输入描述

第一行一个字符串 s，长度不超过 10^5，只包含小写字母。

输出描述

输出一个整数，表示最少需要删除的字符个数。

输入示例

aabbaa

输出示例

1

提示信息

删除一个字符 b，得到 aabaa，是一个合法的字符串。