C. Рудольф и некрасивая строка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Рудольфа есть строка $$$s$$$ длины $$$n$$$. Рудольф считает, что строка $$$s$$$ является некрасивой, если содержит в качестве подстроки$$$^\dagger$$$ хотя бы одну строку «pie» или хотя бы одну строку «map», в противном случае строка $$$s$$$ будет красивой.

Например, «ppiee», «mmap», «dfpiefghmap» — некрасивые строки, а «mathp», «ppiiee» — красивые строки.

Рудольф хочет сократить строку $$$s$$$, удалив некоторые символы, чтобы она стала красивой.

Главный герой не любит напрягаться, поэтому просит вас сделать строку красивой, удалив при этом минимальное количество символов. Он может удалять символы из любых позиций в строке (а не только с начала/конца строки).

$$$^\dagger$$$ Строка $$$a$$$ является подстрокой $$$b$$$, если в строке $$$b$$$ существует последовательный отрезок символов равный $$$a$$$.

Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следуют описания наборов.

Первая строка набора содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^6$$$) — длину строки $$$s$$$.

Следующая строка набора содержит строку $$$s$$$ длины $$$n$$$. Строка $$$s$$$ состоит исключительно из строчных латинских букв.

Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^6$$$.

Выходные данные

Для каждого набора входных данных выведите единственное целое число — минимальное количество символов, которые нужно удалить, чтобы строка $$$s$$$ стала красивой. Если строка изначально красивая, то выведите $$$0$$$.

Пример
Входные данные
6
9
mmapnapie
9
azabazapi
8
mappppie
18
mapmapmapmapmapmap
1
p
11
pppiepieeee
Выходные данные
2
0
2
6
0
2
Примечание

В первом наборе можно удалить, например, $$$4$$$-й и $$$9$$$-й символы, чтобы строка стала красивой.

Во втором наборе строка уже является красивой.