题目描述

铁扇公主最近喜欢上了字符串，但是铁扇公主还想对字符串提出一些苛刻要求，现在她想要好的字符串，具体如下： 一个字符串是好看的，当且仅当其满足的长度为奇数，且任意偶数位的字符与下一个奇数位的字符相同。现在给定一个串，问至少删除多少个字符，可以使它变成好的字符串。 铁扇公主不会解决这个问题，聪明的你可以帮助她解决这个问题吗？

输入格式

输入一个只包含小写字母的字符串 $S$。

输出格式

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

输入输出样例

aabaaba

2

oghoomo

4

说明/提示

样例1解释： 保留的字符串为 aaaaa

数据范围：

$1<=length(S)<=1000000$