#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;
	vector<int> nums;
	for(int i=1;i<=n;i++){
		if(s[i]=='1'){
			k++;
			nums.emplace_back(i);
		}
	}
	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;
		int t=0;
		for(int j=0;j<nums.size();j++){
			if(x<=nums[j]){
				x=nums[j]+i;
				t++;
			}
		}
		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;
}