#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define LL long long

const int N = 2e5 + 5;
int T, n, m, a[N];

inline bool check(int k){
    int cnt = 0;
    for (int i = 1; i <= n; i++){
        if (a[i]){
            cnt++;
            i += k - 1;
        }
    }
    return cnt <= m;
}

int solve(int l, int r){
    if (l == r){
        return l;
    }
    int mid = l + r >> 1;
    if (check(mid)){
        return solve(l, mid);
    }else{
        return solve(mid + 1, r);
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> T;
    while (T--){
        cin >> n >> m;
        char ch;
        for (int i = 1; i <= n; i++){
            cin >> ch;
            a[i] = ch - '0';
        }
        cout << solve(1, n) << endl;
    }

    return 0;
}