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

例如，“piee”，“cxkmmap”，“dcxkfpiefghmap”是丑陋的字符串，而“mathp”，“ppiee”，“cxk”是漂亮的字符串。

hyz觉得这太复杂了想通过删除一些字符来缩短字符串 s，使其美观。

主角不喜欢紧张，所以他要求你通过删除最小数量的字符来使字符串美观。他可以从字符串中的** *个位置删除字符(不仅仅是从字符串的开头或结尾)。

 字符串 a是 b 的子字符串，如果字符串 b中存在等于 a的个连续个字符段。

第一行包含单个整数 t( 1≤t≤10000)—测试用例的数量。下面是测试用例的描述。

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

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

所有测试用例 n的总和不超过 1000000。

对于每个测试用例，输出一个整数—为了使字符串 $s$ 美观，需要删除的最小字符数。如果字符串最初是漂亮的，那么输出 0。

例如，在第一个测试用例中，您可以删除第 44 和第 99 个字符，以使字符串美观。

在第二个测试用例中，字符串已经很漂亮了。