#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;

string s;
int L, k, len;

bool f(int LL)
{
 int cnt = 0;
 for(int i = 0; i < len; i++)
 if(s[i] == '1')
 {
 i += (LL - 1);
 cnt++;
 if(cnt > k)
 return 1;
 }
 return 0;
}

void F(int l, int r)
{
 int m = (l + r) / 2;
 if(f(l) && !f(l + 1))
 L = l + 1;
 else if(f(m))
 F(m, r);
 else
F(l, m - 1);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0); 
 int t;
 cin >> t;
 while(t--)
 {
cin >> len >> k;
 cin >> s;
 L = len / k + 1;
if(len % k == 0)
 L--;
 F(1, L);
 cout << L << endl;
 }
}