#include <bits/stdc++.h>

#define x first
#define y second
#define el '\n'
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int N = 2e5 + 10, INF = 0x3f3f3f3f, mod = 998244353;

char str[N];

void solve() {
    int n, k;
    cin >> n >> k;
    cin >> str + 1;
    int l = 1, r = 2e5, mid;

    auto check = [&](int mid) {
        int cnt = 0;
        for (int i = 1; i <= n; ++i) {
            if (str[i] == '0') continue;
            i += mid - 1, ++cnt;
        }
        return cnt <= k;
    };

    while (l < r) {
        mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l << el;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int tcase = 1;
    cin >> tcase;
    while (tcase--) solve();
}