Cho trước một xâu \(s\) gồm các kí tự chữ cái latin thường. Ta định nghĩa một xâu được gọi là xâu "xấu" nếu nó chứa xâu con "pie" hoặc "map", còn ngược lại thì chúng ta gọi xâu đó là "xâu đẹp"

Nhiệm vụ của bạn là hãy xoá đi một vài kí tự từ xâu \(s\) để biến xâu \(s\) đã cho thành xâu đẹp sao cho số lần xoá là ít nhất có thể (biết rằng, mỗi lần xoá, ta chỉ được phép xoá một kí tự) và in số lần xoá ít nhất này ra màn hình

Input

• Dòng đầu tiên chứa số nguyên dương \(t(1\le t\le 100)\) - Thể hiện số testcase
• \(t\) block tiếp theo, mỗi block có dạng như sau:
• ++ Dòng đầu tiên chứa số nguyên dương \(n(1\le n\le 10^4)\) - Thể hiện đồ dài của xâu \(s\)
• ++ Dòng thứ hai chính là xâu \(s\), chỉ gồm các kí tự chữ cái latin thường

Output

• Ứng với mỗi testcase, hãy in kết quả ra màn hình.

Example

2
3
map
9
mmapnapie

1
2