该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

Rudolf有一个长度为n的字符串s。Rudolf认为如果字符串s包含子串"pie"或者子串"map"，那么这个字符串s就是丑陋的，否则字符串s将被认为是美丽的。

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

Rudolf想要缩短字符串s，通过删除一些字符使其变得美丽。

Rudolf不喜欢短，所以他请你通过删除最少数量的字符来使字符串变得美丽。他可以从字符串的任意位置删除字符（不仅仅是从字符串的开头或结尾）。

如果字符串a是字符串b的子串，那么字符串a是连续的字符串b的一部分。

输入

第一行包含一个整数tt（1≤t≤1e4）—测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数n（1≤n≤1e6）—字符串s的长度。

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

所有测试用例中n的总和不超过1e6。

输出

对于每个测试用例，输出一个整数—需要删除的最小字符数，使得字符串s变得美丽。如果字符串最初就是美丽的，则输出0。

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

2
0
2
6
0
2

Note

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

在第二个测试用例中，字符串已经是美丽的。