Meow Factor 2

고양이 세계에서 털실 뭉치는 오랫동안 인기를 끌어 왔다. 털실 뭉치를 굴리며 나른한 오후를 보내 보지 않은 고양이가 있을까? 최근에는 털실에 경쟁자가 생겼다. 바로 문자열이다. 문자열도 털실만큼 재미있고, 대개 훨씬 안전하다. 지금까지 문자열에 엉켜서 911에 전화를 건 고양이는 없었다.

문자열마다 멋의 차이가 있고, 멋쟁이 고양이는 문자열 놀이를 스타일 있게 즐긴다. 문자열 $S$의 meow factor는 $S$를 "meow"를 부분 문자열로 포함하는 문자열 $S'$로 바꾸는 데 필요한 최소 연산 횟수이다. 연산은 다음 네 가지 중 하나이다:

1. 문자열의 아무 위치에나 임의의 문자를 삽입한다.
2. 문자열의 아무 위치에서나 임의의 문자를 삭제한다.
3. 문자열의 임의의 문자를 임의의 문자로 바꾼다.
4. 인접한 두 문자를 서로 맞바꾼다.

문자열의 meow factor를 계산하는 프로그램을 작성하라.

입력은 한 줄이며, 소문자 'a'부터 'z'까지로만 이루어진 문자열 $S$가 주어진다. $S$의 길이는 1 이상 $10^6$ 이하이다.

$S$의 meow factor를 출력한다.