#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define Sz(x) (int)(x).size()
#define bit(x) (1ll << (x))
using ll = long long;
using db = double;
using ull = unsigned long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vii = vector<vi>;
using vl = vector<ll>;
using vll = vector<vl>;
using vs = vector<string>;
using vd = vector<db>;
mt19937 mrand(time(0));

void solve(void)
{
	int n, k;
	cin >> n >> k;
	string s;
	cin >> s;
	s = ' ' + s;
	int l = 0, r = n + 1;

	auto check = [&](int x)
	{
		int num = 0;

		int u = 1;
		while (u <= n)
		{
			if (s[u] == '1')
			{
				num++;
				u += x;
			}
			else
				u++;
		}
		return num <= k;
	};

	while (l + 1 < r)
	{
		int mid = (l + r) / 2;
		if (check(mid)) r = mid;
		else l = mid;
	}
	cout << r << "\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	// cout << fixed << setprecision(10);

	int T = 1;
	cin >> T;
	for (int i = 1; i <= T; i++)
	solve();

	return 0;
}