题目描述

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 翻译

样例

6
9
mmapnapie
9
azabazapi
8
mappppie
18
mapmapmapmapmapmap
1
p
11
pppiepieeee

2
0
2
6
0
2