Kirin has provided Office his leave plan for the next N days. Leave plan is in the form of a string containing P and A, where P means Kirin is going to take leave on that day, and A means Kirin is going to office on that day. We all know Kirin loves to go on a random Date to refresh his mind from the heavy workload of the office. So now, he wants to change his leave plan. That means changing A to P or P to A .But office has told him that he can change at most M days of the plan. Now Kirin wants to change his plan in such a way that the size of the maximum consecutive block of P and A is minimized.
The first line of the input is an integer T(1 <= T <= 100) , denoting the number of test cases.Each test case has two lines. The first line contains a single integers N(1<= N <= 100000) and M(0 <= M <= N) .The next line contains a string of length N , of which the i-th character is either A or P
There will be T lines of output in the form of "Case X: Y". where X is the case number and Y is the minimum size of the maximum consecutive block of days.
Input | Output |
---|---|
2 5 2 APPPA 6 2 AAPPPA | Case 1: 1 Case 2: 1 |