题目描述

薯条哥有一个字符串，现在他想问你，最少需要删掉多少个字符，才可以使字符串变成一个好串。

对于薯条哥来说，一个好串的长度必须是偶数，且满足当串的下标从 $0$ 开始，那么当 $i$ 是偶数，都有 $s_i=s_{i+1}$。

输入描述

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

输出描述

输出一个数，表示最少需要删除的字符数量，才能使得字符串变为一个好串。

样例

输入

abbcdd

输出

2

样例解释

删除 a 和 c 后，字符串变为了 bbdd ，是一个好串。