Hide

Problem D
Meow Factor 2

/problems/meowfactor2/file/statement/en/img-0001.jpg

Picture by Stefan Tell on Flickr, cc by

Strings of yarn have been popular in Catland for ages. Which cat has not spent many a lazy afternoon bouncing around a ball of yarn? Lately however, strings of yarn have gotten competition: strings of characters. It turns out that these are almost as much fun as yarn, and generally much safer as well (so far, no cat has had to call 911 on account of any character string-related entanglement accidents).

Naturally, some strings are more stylish than others, and for cool cats it is important to engage in their string-playing pastime with style. The meow factor of a string $S$ is the minimum number of operations needed to transform $S$ into a string $S’$ which contains the word “meow” as a substring, where an operation is one of the following four:

Insert an arbitrary character anywhere into the string.
Delete an arbitrary character anywhere from the string.
Replace any character in the string by an arbitrary character.
Swap any two adjacent characters in the string.

Write a program to compute the meow factor of a string of characters.

Input

The input consists of a single line containing a string $S$, consisting only of lower-case letters ‘a’-‘z’. The length of $S$ is at least $1$ and at most $10^6$.

Output

Output the meow factor of $S$.

Sample Input 1	Sample Output 1
pastimeofwhimsy	1

Sample Input 2	Sample Output 2
yarn	4

Problem DMeow Factor 2

Input

Output

Problem D
Meow Factor 2