CF1941C.Rudolf and the Ugly String

Rudolf has a string $s$ of length $n$. Rudolf considers the string $s$ to be ugly if it contains the substring$^\dagger$ "pie" or the substring "map", otherwise the string $s$ will be considered beautiful.

For example, "ppiee", "mmap", "dfpiefghmap" are ugly strings, while "mathp", "ppiiee" are beautiful strings.

Rudolf wants to shorten the string $s$ by removing some characters to make it beautiful.

The main character doesn't like to strain, so he asks you to make the string beautiful by removing the minimum number of characters. He can remove characters from any positions in the string (not just from the beginning or end of the string).

$^\dagger$ String $a$ is a substring of $b$ if there exists a consecutive segment of characters in string $b$ equal to $a$.

鲁道夫有一个长度为 $n$ 的字符串 $s$。如果字符串 $s$ 包含子串$^\dagger$ "pie" 或子串 "map"，则鲁道夫认为该字符串是丑陋的；否则，字符串 $s$ 被视为优美的。

例如，"ppiee"、"mmap"、"dfpiefghmap" 是丑陋的字符串，而 "mathp"、"ppiiee" 是优美的字符串。

鲁道夫希望通过对字符串 $s$ 删除若干字符来使其变得优美。

主角不喜欢费力，因此他请你通过删除最少数量的字符来使字符串变得优美。你可以从字符串的任意位置（不仅限于开头或结尾）删除字符。

$^\dagger$ 若字符串 $a$ 在字符串 $b$ 中存在一段连续的字符段与之完全相等，则称 $a$ 是 $b$ 的一个子串。

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The descriptions of the test cases follow.

The first line of each test case contains a single integer $n$ ($1 \le n \le 10^6$) — the length of the string $s$.

The next line of each test case contains the string $s$ of length $n$. The string $s$ consists of lowercase Latin letters.

The sum of $n$ over all test cases does not exceed $10^6$.

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 10^6$）—— 表示字符串 $s$ 的长度。

每个测试用例的第二行包含一个长度为 $n$ 的字符串 $s$，该字符串由小写拉丁字母组成。

所有测试用例的 $n$ 值之和不超过 $10^6$。

For each test case, output a single integer — the minimum number of characters that need to be deleted to make the string $s$ beautiful. If the string is initially beautiful, then output $0$.

对于每个测试用例，输出一个整数——使字符串 $s$ 变为优美字符串所需删除的最少字符数。如果字符串初始即为优美字符串，则输出 $0$。

In the first test case, for example, you can delete the $4$th and $9$th characters to make the string beautiful.

In the second test case, the string is already beautiful.

在第一个测试用例中，例如，你可以删除第 $4$ 个和第 $9$ 个字符，使该字符串变得优美。

在第二个测试用例中，该字符串本身已经是优美的。