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

signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int T; cin >> T;
    while (T--) {
        int n, lmt; cin >> n >> lmt;
        string state; cin >> state;
        state = " " + state;
        
        bool flag = 1;
        for (int i = 1; i <= n; ++i) {
        	if (state[i] == '1') {
        		flag = 0;
			}
		}
		if(flag) {
			cout << "0\n";
			continue;
		}
        
        auto check = [&](int L) {
//        	cout << L << '\n';
            int cnt = 0;
            string tmp = state;
            for (int i = 1; i <= n; ++i) {
                if (tmp[i] == '1') {
                    int Len = i + L - 1;
                    for (; i <= Len and i <= n; ++i) {
                        tmp[i] = '0';
                    }
                    i--;
                    cnt++;
                }
            }
            
//            cout << L << " " << cnt << '\n';
            return cnt <= lmt;
        };
//        cout << "helloworld\n";
        int l = 1, r = n;
        while (l < r) {
            int mid = (l + r) >> 1;
//            cout << mid << '\n';
            if (check(mid)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        cout << l << '\n';
    }
}