#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=200005;
int n,m;
string s;
int l,r;
void solve(){
	cin>>n>>m;
	cin>>s;s=' '+s;
	int k=0;
	for(int i=1;i<=n;i++){
		if(s[i]=='1')k++;
	}
	for(int i=1;i<=n;i++){
		if(s[i]=='1'){
			l=i;break;
		}
	}
	for(int i=n;i>=1;i--){
		if(s[i]=='1'){
			r=i;break;
		}
	}
	for(int i=k/m;i<=r-l+1;i++){
		int x=1,d=i;
		int t=0;
		while(x<=n){
			while(s[x]=='0'){
				x++;
			}
			if(s[x]=='1'){
				x=x+i;t++;
			}
			if(t>m)break;
		}
		if(x<=n){
			continue;
		}
		else if(t<=m){
			cout<<i<<endl;
			return;
		}
	}	
	return;
}
signed main() {
	//ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	int t=1;
	cin>>t;
	while(t--){
		solve();
	}
    return 0;
}