You are given a binary string S of length N, and a value K. You need to find a maximum length of a beautiful string which is a sub-string of S. A beautiful string is a binary string where absolute difference of zero’s and one’s occurrence is no more than K.
Input starts with a value T<=100 (Total number of test case).
For every input first line contains 1<=N<=1000000 and 0<=K<=N. And next line contains a binary string of length N.
Output format is Case X: Y where X is the case number test case and Y is the maximum length of the Beautiful String.
| Input | Output |
|---|---|
2 7 2 0101000 7 1 0101000 | Case 1: 6 Case 2: 5 |