#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <stdio.h>
using namespace std;
 
int T;
int n,k;
int arr[1001001],m=0;
string st;

struct nod{
	int val;
	int ind;
	nod(int v,int i){
		val=v;
		ind=i;
	}
};

bool operator<(nod a, nod b){
	return a.val > b.val;
}
priority_queue<nod> last_one;
priority_queue<nod> last_zero;
bool check(int x){
	/*int ret=0;
	for(int i=0;i<m;i++){
		ret+=arr[i]/(x+1);
	}
	return ret<=k;*/

	while(!last_one.empty()){
		last_one.pop();
	}
	while(!last_zero.empty()){
		last_zero.pop();
	}
	last_one.push(nod(0,-1));
	last_zero.push(nod(0,-1));

	int sol;
	int cnt_zero=0;
	int cnt_one=0; 
	for(int i=0;i<n;i++){
		while(i-last_one.top().ind>x){
			last_one.pop();
		}
		while(i-last_zero.top().ind>x){
			last_zero.pop();
		}
		if(st[i]=='0'){
			cnt_zero++;
		} else {
			cnt_one++;
		}
		int dp_one=last_zero.top().val  + cnt_zero;
		int dp_zero=last_one.top().val  + cnt_one;
		if(i==n-1){
			sol=min(dp_one,dp_zero);
		}
		last_one.push(nod(dp_one - cnt_one,i));
		last_zero.push(nod(dp_zero - cnt_zero,i));
	}
	return sol<=k;
}
 
int main(){
	//freopen("07.txt","r",stdin);
	//freopen("07o.txt","w",stdout);
	cin>>T;
	while(T--){
		cin>>n>>k;
		cin>>st;
		m=0;
		int mn=0,mn2=0;
		for(int i=0;i<n;i++){
			if(i%2){
				if(st[i]=='1'){
					mn++;
				}
				if(st[i]=='0'){
					mn2++;
				} 
			} else {
				if(st[i]=='0'){
					mn++;
				}
				if(st[i]=='1'){
					mn2++;
				} 
			}
		}
		if(k>=mn || k>=mn2){
			cout<<1<<endl;
			continue;
		}
		arr[0]=1;
		m++;
		for(int i=1;i<n;i++){
			if(st[i]==st[i-1]){
				arr[m-1]++;
			} else {
				arr[m]=1;
				m++;
			}
		}
 
		int ll=1,rr=n;
		while(rr-ll>1){
			int mid=(rr+ll)/2;
			if(check(mid)){
				rr=mid;
			} else {
				ll=mid;
			}
		}
		cout<<rr<<endl;
	}
}