311147: CF1941C. Rudolf and the Ugly String
Description
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$.
InputThe 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$.
OutputFor 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$.
ExampleInput6 9 mmapnapie 9 azabazapi 8 mappppie 18 mapmapmapmapmapmap 1 p 11 pppiepieeeeOutput
2 0 2 6 0 2Note
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.
Output
鲁道夫有一个长度为 $ n $ 的字符串 $ s $。如果字符串 $ s $ 包含子字符串 "pie" 或 "map"，则鲁道夫认为这个字符串是丑陋的，否则认为是美丽的。鲁道夫希望通过删除一些字符来缩短字符串 $ s $，使其变得美丽。他希望删除最少的字符数量。可以从字符串的任何位置删除字符。
**输入数据格式：**
第一行包含一个整数 $ t $（$ 1 \le t \le 10^4 $），表示测试用例的数量。接下来是每个测试用例的描述。
每个测试用例的第一行包含一个整数 $ n $（$ 1 \le n \le 10^6 $），表示字符串 $ 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 个字符使字符串变得美丽。
- 在第二个测试用例中，字符串已经是美丽的。**题目大意：** 鲁道夫有一个长度为 $ n $ 的字符串 $ s $。如果字符串 $ s $ 包含子字符串 "pie" 或 "map"，则鲁道夫认为这个字符串是丑陋的，否则认为是美丽的。鲁道夫希望通过删除一些字符来缩短字符串 $ s $，使其变得美丽。他希望删除最少的字符数量。可以从字符串的任何位置删除字符。 **输入数据格式：** 第一行包含一个整数 $ t $（$ 1 \le t \le 10^4 $），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 $ n $（$ 1 \le n \le 10^6 $），表示字符串 $ 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 个字符使字符串变得美丽。 - 在第二个测试用例中，字符串已经是美丽的。