在猫国，毛线球已经流行了很久。哪只猫没有在慵懒的午后围着毛线球玩耍过呢？然而最近，字符组成的字符串成了毛线球的竞争对手。事实证明，这些字符串和毛线球一样有趣，而且通常安全得多（到目前为止，还没有猫因为字符字符串相关的缠绕事故而拨打 911）。

自然地，有些字符串比其他的更时髦，对于酷猫来说，有格调地进行字符串游戏非常重要。一个字符串 $S$ 的“喵因子”（meow factor）是指将 $S$ 转换为包含子串 “meow” 的字符串 $S'$ 所需的最少操作次数，其中操作包括以下四种：

1. 在字符串的任意位置插入一个任意字符。
2. 删除字符串中任意位置的一个字符。
3. 将字符串中的任意字符替换为任意字符。
4. 交换字符串中任意两个相邻的字符。

编写一个程序来计算给定字符串的喵因子。

图片由 Stefan Tell 在 Flickr 上提供，采用 cc by 协议

输入格式

输入包含一行，为一个字符串 $S$，仅由小写字母 ‘a’-‘z’ 组成。$S$ 的长度至少为 1，至多为 $10^6$。

输出格式

输出 $S$ 的喵因子。

样例

样例输入 1

pastimeofwhimsy

样例输出 1

1

样例输入 2

yarn

样例输出 2

4