Chef is a well-known chef, and everyone wishes to taste his dishes.

As you might know, cooking is not an easy job at all and cooking everyday makes the chef very tired. So, Chef has decided to give himself some days off.

Chef has made a schedule for the next N days: On i-th day if A_i is equal to 1 then Chef is going to cook a delicious dish on that day, if A_i is equal to 0 then Chef is going to rest on that day.

After Chef made his schedule he discovered that it's not the best schedule, because there are some big blocks of consecutive days where Chef will cook which means it's still tiring for Chef, and some big blocks of consecutive days where Chef is going to rest which means chef will be bored doing nothing during these days.

Which is why Chef has decided to make changes to this schedule, but since he doesn't want to change it a lot, he will flip the status of at most K days. So for each day which Chef chooses, he will make it 1 if it was 0 or he will make it 0 if it was 1.

Help Chef by writing a program which flips the status of at most K days so that the size of the maximum consecutive block of days of the same status is minimized.

Input

The first line of the input contains an integer T denoting the number of test cases.

The first line of each test case contains two integers: N denoting the number of days and K denoting maximum number of days to change.

The second line contains a string of length N , of which the i-th character is 0 if chef is going to rest on that day, or 1 if chef is going to work on that day

Output

For each test case, output a single line containing a single integer, which is the minimum possible size of maximum block of consecutive days of the same status achievable.

Constraints

• 1 ≤ T ≤ 11,000
• 1 ≤ N ≤ 10⁶
• The sum of N in all test-cases won't exceed 10⁶.
• 0 ≤ K ≤ 10⁶
• 0 ≤ A_i ≤ 1

Subtasks

• Subtask #1 (20 points): N ≤ 10
• Subtask #2 (80 points): Original Constraints

Example

Input:29 21100011114 11001Output:22

Explanation

Example case 1: The answer is 2 because we can change the string to: 110101011

Example case 2: If we don't change the input string at all, the answer will be 2. It is the best value we can achieve under the given conditions.

 

这么好写的二分题，考场上居然没有调出来【已经哭晕在厕所】

二分答案，假如有一段满足$gap_i \geq mid+1$，那么显然这里需要进行一次调整

调整次数为：$\frac{gap_i}{mid+1}$

这个很好想，每隔$mid$个相同的调整一个，如果恰好在最后一个位置要调整，改成在倒数第二个调整即可

如：当$mid=3$时

$111011101110\rightarrow111011101101$

需要特判为1的情况（因为若最后一位改成倒数第二位，倒数第三位和倒数第二位就会连起来）

 

 

#include
     
      using namespace std;const int N=1e6+5;int n,k;char ss[N];vector
      
        gap;bool check(int x){    int ret=0;    for(int i=0;i
       
        >1;            if(check(mid)) r=mid;            else l=mid;        }        printf("%d\n",r);    }    return 0;}