Pizza or Broccoli

All submissions for this problem are available.

### Read problem statements in [Bengali](http://www.codechef.com/download/translated/LTIME78/bengali/PIBRO.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/LTIME78/mandarin/PIBRO.pdf), [Russian](http://www.codechef.com/download/translated/LTIME78/russian/PIBRO.pdf), and [Vietnamese](http://www.codechef.com/download/translated/LTIME78/vietnamese/PIBRO.pdf) as well. On each of the following $N$ days (numbered $1$ through $N$), Chef is planning to cook either pizza or broccoli. He wrote down a string $A$ with length $N$, where for each valid $i$, if the character $A_i$ is '1', then he will cook pizza on the $i$-th day, while if $A_i$ is '0', he will cook broccoli on this day. Chefu, his son, loves pizza but hates broccoli ― just like most kids. He wants to select a substring of $A$ with length $K$ and change each character '0' in this substring to '1'. Afterwards, let's define *pizza time* as the maximum number of consecutive days where Chef will cook pizza. Find the maximum pizza time Chefu can achieve. ### Input - The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows. - The first line of each test case contains two space-separated integers $N$ and $K$. - The second line contains a string $A$ with length $N$. ### Output For each test case, print a single line containing one integer ― the maximum pizza time. ### Constraints - $1 \le T \le 1,000$ - $1 \le K \le N \le 10^5$ - $A$ contains only characters '0' and '1' - the sum of $N$ over all test cases does not exceed $10^6$ ### Subtasks **Subtask #1 (50 points):** - $N \le 10^3$ - the sum of $N$ over all test cases does not exceed $10^4$ **Subtask #2 (50 points):** original constraints ### Example Input ``` 2 13 2 0101110000101 6 3 100001 ``` ### Example Output ``` 5 4 ``` ### Explanation **Example case 1:** Chefu can choose the substring $A[2, 3]$ = "10", and change the third character of $A$ to '1'. Then, the pizza time is $5$ days: from day $2$ to day $6$. **Example case 2:** Chefu can choose the substring $A[2, 4]$ = "000". Then, the pizza time is $4$ days: from day $1$ to day $4$.