← 返回题目列表

Codeforces · 1941/C

C. 鲁道夫和丑陋的绳子

中文机器翻译题面 查看原题

Rudolf 有一个长度为 $$$n$$$ 的字符串 $$$s$$$。如果字符串 $$$s$$$ 包含子字符串 $$$^\dagger$$$ "pie" 或子字符串 "map",鲁道夫认为字符串 $$$s$$$ 是丑陋的,否则字符串 $$$s$$$ 将被认为是美丽的。

例如,“ppiee”、“mmap”、“dfpiefghmap”是丑陋的字符串,而“mathp”、“ppiiee”是漂亮的字符串。

Rudolf 希望通过删除一些字符来缩短字符串 $$$s$$$ 以使其美观。

主角不喜欢紧张,所以他要求你通过删除最少数量的字符来使字符串变得漂亮。他可以从字符串中的任何位置删除字符(不仅仅是从字符串的开头或结尾)。

$$$^\dagger$$$ 如果字符串 $$$b$$$ 中存在等于 $$$a$$$ 的连续字符段,则字符串 $$$a$$$ 是 $$$b$$$ 的子字符串。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^6$$$) — 字符串 $$$s$$$ 的长度。

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

所有测试用例的 $$$n$$$ 总和不超过 $$$10^6$$$。

输出

对于每个测试用例,输出一个整数 - 为使字符串 $$$s$$$ 美观而需要删除的最小字符数。如果字符串最初很漂亮,则输出$$$0$$$。

示例

输入 #1

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

输出 #1

2
0
2
6
0
2

注意

例如,在第一个测试用例中,您可以删除第 $$$4$$$ 和第 $$$9$$$ 个字符,以使字符串美观。

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