Đ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
cứu
hết cứu :))