#include <bits/stdc++.h>
using namespace std;
#define int long long
int t;
bool check(string str, int mid, int k) {
	int ans = 0;
	for (int i = 0; i < str.size(); i++) {
		if (i + mid - 1 >= str.size()) { 
			for(int j=i;j<str.size();j++){
				if(str[i] == '1'){
					ans ++;
					break;
				}
			}
			break;
		}
		if (str[i] == '1') {
			i = i + mid - 1;
			ans++;
		}
	}
	if (ans <= k) {
		return true;
	}
	return false;
}
signed main() {
	cin >> t;
	while (t--) {
		int n,  k;
		string s;
		cin >> n >> k;
		cin >> s;
		int l = 1, r = n;
		int mid;
		while (l < r) {
			mid = (l + r) >> 1;
			if (check(s, mid, k) == true) {
				r = mid;
			} else {
				l = mid + 1;
			}
		}
		cout << l << endl;
	}
	return 0;
}