Limits 500ms, 512 MB

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.

Input

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

Output

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.

Sample

InputOutput
2
5 2
APPPA
6 2
AAPPPA
Case 1: 1
Case 2: 1

Submit

Login to submit.

Statistics

33% Solution Ratio
kzvd4729Earliest, Apr '19
nusuBotFastest, 0.1s
ovis96Lightest, 524 kB
ovis96Shortest, 1292B
Toph uses cookies. By continuing you agree to our Cookie Policy.