#include<bits/stdc++.h>
#define endl '\n'
#define fast() ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define _ int _T; cin >> _T; while(_T --) 
#define int long long

using namespace std;

const int mod = 1e9 + 7;
int n,k;
string s;

int check(int x){
	int ans = 0;
	for(int i = 0;i < n;){
		if(s[i] == '0'){
			i ++;
			continue;
		}
		i += x;
		ans ++;
	}
	return ans <= k;
}

void solve(){
	cin >> n >> k;
	cin >> s;
	int l = 1,r = n;
	while(l < r){
		int mid = l + r >> 1;
		if(check(mid)) r = mid;
		else l = mid + 1;
	} cout << l << endl;
}

signed main(){
//	fast();
	_
	solve();
	return 0;
}