#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

void solve(){
	int n,k;
	cin>>n>>k;
	string s;
	cin>>s;
	s=" "+s;

	int l=1,r=2e5+10,mid;

	auto check=[&](int x){
		int ls=0,rs=0,cnt=0;
		for(int i=1;i<=n;i++){
			if(s[i]=='1'){
				if(i>=ls&&i<=rs) continue;
				else{
					cnt++;
					// cout<<i<<' '<<ls<<' '<<rs<<' '<<cnt<<'\n';
					ls=i,rs=i+x-1;
				}
			}
		}
		return cnt<=k;
	};

	while(l<=r){
		mid=l+(r-l)/2;
		// cout<<l<<' '<<mid<<' '<<r<<'\n';
		if(check(mid)) r=mid-1;
		else l=mid+1;
	}

	cout<<l<<'\n';

}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);

	int t;
	cin>>t;
	while(t--){
		solve();
	}
	return 0;
}