#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
const int N = 1e6 + 5;
#define int long long
typedef pair<int, int> PII;
#define MAX LONG_LONG_MAX
int ar[N];
void solve()
{
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    s = " " + s;
    for (int i = 1; i <= n; i++)
    {
        if (s[i] == '1')
            ar[i] = 1;
        else
            ar[i] = 0;
    }

    int l = 0, r = n + 1;
    while (l + 1 < r)
    {
        int mid = (l + r) >> 1;
        int cnt = 0;
        for (int i = 1; i <= n; i++)
        {
            while (i <= n && ar[i] == 0)
                i++;
            if (i > n)
                break;
            i += mid - 1;
            cnt++;
        }

        if (cnt <= k)
            r = mid;
        else
            l = mid;
    }
    cout << r << endl;
}
signed main()
{
    int tcase;
    cin >> tcase;
    while (tcase--)
        solve();
    return 0;
}