C. Rudolf and the Ugly String

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Rudolf has a string s� of length n�. Rudolf considers the string s� to be ugly if it contains the substring†† "pie" or the substring "map", otherwise the string s� will be considered beautiful.

For example, "ppiee", "mmap", "dfpiefghmap" are ugly strings, while "mathp", "ppiiee" are beautiful strings.

Rudolf wants to shorten the string s� by removing some characters to make it beautiful.

The main character doesn't like to strain, so he asks you to make the string beautiful by removing the minimum number of characters. He can remove characters from any positions in the string (not just from the beginning or end of the string).

†† String a� is a substring of b� if there exists a consecutive segment of characters in string b� equal to a�.

Input

The first line contains a single integer t� (1≤t≤1041≤�≤104) — the number of test cases. The descriptions of the test cases follow.

The first line of each test case contains a single integer n� (1≤n≤1061≤�≤106) — the length of the string s�.

The next line of each test case contains the string s� of length n�. The string s� consists of lowercase Latin letters.

The sum of n� over all test cases does not exceed 106106.

Output

For each test case, output a single integer — the minimum number of characters that need to be deleted to make the string s� beautiful. If the string is initially beautiful, then output 00.

Example

input

Copy

6

9

mmapnapie

9

azabazapi

8

mappppie

18

mapmapmapmapmapmap

1

p

11

pppiepieeee

output

Copy

2
0
2
6
0
2

Note

In the first test case, for example, you can delete the 44th and 99th characters to make the string beautiful.

In the second test case, the string is already beautiful.

解题说明：此题是一道字符串题，直接遍历，每次读取三个字母，如果存在不满足的字符串，剔除中间的字母，继续遍历。

#include<stdio.h>
char s[1000001];
int main() 
{
	int t, n;
	scanf("%d", &t);
	while (t--) 
	{
		scanf("%d", &n);
		scanf("%s", s);
		int u1 = 0;
		for (int i = 0; i < n; i++) 
		{
			if ((s[i] == 'm' && s[i + 1] == 'a' && s[i + 2] == 'p') || (s[i] == 'p' && s[i + 1] == 'i' && s[i + 2] == 'e')) 
			{
				u1++;
				i += 2;
			}
		}
		printf("%d\n", u1);
	}
	return 0;
}