题目内容

小明是一位热爱字符串分析的程序员。今天他提出了一个有趣的概念：对于一个由小写字母组成的非空字符串，如果其中出现次数为奇数的字母种类不超过 1，则称该字符串是“平衡的”。例如，zz 中字母 z 出现 2 次（偶数），奇数次字母种类数为 0，是平衡的；aba 中只有 b 出现 1 次（奇数），种类数为 1，也是平衡的；cccg 中 c 出现 3 次（奇数），g 出现 1 次（奇数），奇数次字母种类数为 2，不是平衡的。

现在给定一个只包含小写字母的字符串 $s$，你需要将它划分成尽可能少的连续非空子串，使得每个子串都是平衡的。请问最少可以划分成多少段？

字符串的长度 $n$ 满足 $1 \le n \le 10^5$。所有字符均为小写字母。

输入描述

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