У Рудольфа есть строка \(s\) длины \(n\). Рудольф считает, что строка \(s\) является некрасивой, если содержит в качестве подстроки\(^\dagger\) хотя бы одну строку «pie» или хотя бы одну строку «map», в противном случае строка \(s\) будет красивой.
Например, «ppiee», «mmap», «dfpiefghmap» — некрасивые строки, а «mathp», «ppiiee» — красивые строки.
Рудольф хочет сократить строку \(s\), удалив некоторые символы, чтобы она стала красивой.
Главный герой не любит напрягаться, поэтому просит вас сделать строку красивой, удалив при этом минимальное количество символов. Он может удалять символы из любых позиций в строке (а не только с начала/конца строки).
\(^\dagger\) Строка \(a\) является подстрокой \(b\), если в строке \(b\) существует последовательный отрезок символов равный \(a\).
Выходные данные
Для каждого набора входных данных выведите единственное целое число — минимальное количество символов, которые нужно удалить, чтобы строка \(s\) стала красивой. Если строка изначально красивая, то выведите \(0\).
Примечание
В первом наборе можно удалить, например, \(4\)-й и \(9\)-й символы, чтобы строка стала красивой.
Во втором наборе строка уже является красивой.