// lhzawa(https://www.cnblogs.com/lhzawa/)
// Problem: E. Turn It Off
// Contest: QOJ - The 2019 ICPC China Shaanxi Provincial Programming Contest
// URL: https://qoj.ac/contest/1285/problem/6726
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
char s[N];
int main() {
	function<void ()> solve = []() -> void {
		int n, k;
		scanf("%d%d%s", &n, &k, s + 1);
		int l = 1, r = n, ans = n;
		function<int (int)> check = [&n, &k](int l) -> int {
			int c = 0;
			for (int i = 1; i <= n; ) {
				if (s[i] == '1') {
					i += l, c++;
				}
				else {
					i++;
				}
			}
			return c <= k;
		};
		for (; l <= r; ) {
			int mid = (l + r) >> 1;
			if (check(mid)) {
				ans = mid, r = mid - 1;
			}
			else {
				l = mid + 1;
			}
		}
		printf("%d\n", ans);
		return ;
	};
	int _;
	scanf("%d", &_);
	for (; _; _--) {
		solve();
	}
	return 0;
}