Xâu đẹp

Xem PDF



Tác giả:
Dạng bài
Điểm: 888 Thời gian: 2.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

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

Test 1

Input
2
3
map
9
mmapnapie
Output
1
2
Note
  • Ứng với ví dụ 1, ta có thể xoá đi kí tự đầu tiên để thu được xâu đẹp
  • Ứng với ví dụ 2, ta có thể xoá đi kí tự thứ 4 và kí tự thứ 9 để thu được xâu đẹp

Bình luận