CF1941C Rudolf and the Ugly String

Rudolf 有一个长度为 $n$ 的字符串 $s$。如果字符串 $s$ 包含子串“pie”或子串“map”，Rudolf 就认为这个字符串是丑陋的，否则就认为字符串 $s$ 是美丽的。 例如，“ppiee”、“mmap”、“dfpiefghmap”是丑陋的字符串，而“mathp”、“ppiiee”是美丽的字符串。 Rudolf 想通过删除一些字符来让字符串 $s$ 变得美丽。 主角不喜欢费力，所以他希望你通过删除最少数量的字符，使字符串变得美丽。他可以从字符串的任意位置删除字符（不仅仅是开头或结尾）。 $^\dagger$ 字符串 $a$ 是字符串 $b$ 的子串，当且仅当在字符串 $b$ 中存在一段连续的字符与 $a$ 完全相同。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 10^6$），表示字符串 $s$ 的长度。 接下来一行包含长度为 $n$ 的字符串 $s$。字符串 $s$ 仅由小写拉丁字母组成。 所有测试用例中 $n$ 的总和不超过 $10^6$。

对于每个测试用例，输出一个整数，表示为了使字符串 $s$ 变得美丽，最少需要删除的字符数。如果字符串本身就是美丽的，则输出 $0$。

在第一个测试用例中，例如，你可以删除第 $4$ 个和第 $9$ 个字符，使字符串变得美丽。 在第二个测试用例中，字符串本身就是美丽的。 由 ChatGPT 4.1 翻译