#include<bits/stdc++.h>
using namespace std;
#define ll long long
string x;
ll n,k;
bool check(ll len){
	ll now=0,need=0;
	while(now<=n){
		if(x[now]=='1'){
			need++;
			now+=len;
		}
		else {
			now++;
		}
	}
	return need<=k;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t;cin>>t;
	while(t--) {
		cin>>n>>k;
		cin>>x;
		ll l=1,r=n,ans=0;
		while(l<=r) {
			ll mid=(l+r)/2;
			if(check(mid)) {
				r=mid-1;
				ans=mid;
			}
			else {
				l=mid+1;
			}
		}
		cout<<ans<<"\n";
	}
}