#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
string s;
int x,y;
bool check(int mid)
{
	int cnt = 0 ;
	for(int i = 0 ; i < x ; )
	{
		if(s[i]=='1')
		{
			cnt++;
			i+=mid;
		}
		else i++;
	}
	return cnt<=y;
}
void slove()
{


	cin>>x>>y;
	cin>>s;

	int l = 1,r=x;
	while(l<r)
	{
		int mid = (l+r)/2;
		if(check(mid)) r=mid;
		else l = mid+1;
	}
	cout<<l<<endl;
}
int main()
{
	int tcase;
	cin>>tcase;
	while(tcase--)
	{
		slove();
	}
}