Maximising Vactions

You are given Chef's calendar for the next N$N$ days, defined as a binary string S$S$ of length N$N$ where Si=0$S_i=0$ means that Chef has a holiday on the ith$i^{th}$ day from now, and Si=1$S_i=1$ means that Chef has to work on that day.

Chef wants to plan his vacations. For each vacation, Chef needs X$X$ consecutive holidays in his calendar. Obviously, he can only go on one vacation at a time.

Chef can take at most one extra holiday. That is, he can flip at most one digit in S$S$ from 1$1$ to 0$0$. If he does this optimally, what is the maximum number of vacations that he can go on?

Input Format

• The first line of input contains a single integer T$T$, denoting the number of test cases. The description of T$T$ test cases follows.
• The first line of each test case contains two space-separated integers N$N$ and X$X$.
• The second line of each test case contains a binary string S$S$ of length N$N$ — Chef's schedule.

Output Format

For each test case, output on a new line the answer — the maximum number of vacations Chef can take if he takes at most one more extra holiday.

Constraints

• 1≤T≤1000$1\le T\le 1000$
• 1≤N≤2⋅105$1\le N\le 2\cdot {10}^5$
• 1≤X≤N$1\le X\le N$
• The sum of N$N$ across all test cases does not exceed 2⋅105$2\cdot {10}^5$

Sample Input 1 

3
7 2
0010001
4 3
1010
5 2
00100

Sample Output 1 

3
1
2

Explanation

Test Case 1$1$: Chef can flip the 3rd$3^{rd}$ digit to make his calendar 0000001$0000001$. This allows him to take 3$3$ vacations in the first 6$6$ days.

Test Case 2$2$: Chef can flip the 3rd$3^{rd}$ digit to make his calendar 1000$1000$. This allows him to take one vacation using the last 3$3$ days.

Test Case 3$3$: Regardless of whether Chef flips the 3rd$3^{rd}$ digit or not, he can take at most 2

Solution:

Solution: