一个鲜为人知的事实是，奶牛拥有自己的文字：「牛文」。牛文由 26 个字母 'a' 到 'z' 组成，但是当奶牛说牛文时，可能与我们所熟悉的 'abcdefghijklmnopqrstuvwxyz' 不同，她会按某种特定的顺序排列字母。为了打发时间，Bessie 的表妹 Mildred 在反复哼唱牛文字母歌，而 Farmer Nhoj 好奇她唱了多少遍。

给定一个小写字母组成的字符串，为 Farmer Nhoj 听到 Mildred 唱的字母，计算 Mildred 至少唱了几遍完整的牛文字母歌，使得 Farmer Nhoj 能够听到给定的字符串。Farmer Nhoj 并不始终注意 Mildred 所唱的内容，所以他可能会漏听 Mildred 唱过的一些字母。给定的字符串仅包含他记得他所听到的字母。

注意：本题每个测试点的时间限制为默认限制的两倍。

输入格式（从终端/标准输入读入）：

输入仅一行，包含一个小写字母组成的字符串，为 Farmer Nhoj 听到 Mildred 唱的字母。字符串的长度不小于 1 且不大于 10$^5$。

输出格式（输出至终端/标准输出）：

输出 Mildred 所唱的完整的牛文字母歌的最小次数。

输入样例：

mildredree

输出样例：

3

Mildred 至少唱了三遍牛文字母歌。有可能 Mildred 只唱了三遍牛文字母歌，如果牛文字母表以 "mildre" 开头，并且 Farmer Nhoj 听到了以下被标记为大写的字母。

MILDREabcfghjknopqstuvwxyz
milDREabcfghjknopqstuvwxyz
mildrEabcfghjknopqstuvwxyz

测试点性质：

• 测试点 1-5 中，Farmer Nhoj 仅听到出现在 Mildred 或 Bessie 的名字中的字母。
• 测试点 6-16 中，Farmer Nhoj 从未听到任何出现在 Mildred 名字中的字母。