#include <bits/stdc++.h>
#define boAshraf ios_base::sync_with_stdio(false); cin.tie(NULL);
#define ll long long
#define sz(s) (int)(s).size()
#define all(s) (s).begin(),(s).end()
using namespace std;
void File();
void sol();
int main() {
    boAshraf
//    File();
    freopen("strips.in", "r", stdin);
    int t = 1;
    cin >> t;
    while (t--) {
        sol();
    }
    return 0;
}

void sol() {
    int n,k;
    cin>>n>>k;
    vector<pair<int,int>>v;
    string s;cin>>s;
    int cnt=0,bad=0;
    char last=s[0];
    for (int i = 0; i < n; ++i) {
        if(i && s[i]!=s[i-1])bad++;
        if(s[i]==last)cnt++;
        else{
            if(last=='0'){
                v.emplace_back(cnt,2);
            }
            cnt=1;
            last=s[i];
        }
    }
    if(last=='0')v.emplace_back(cnt,1);
    if(s[0]=='0')v[0].second=1;
    if(v.empty() || v[0].first==n)return void(cout<<0<<'\n');
    int ans=bad;
    vector<vector<int>>op(2);
    for(auto [a,b]:v){
        op[b-1].emplace_back(a);
    }
    sort(all(op[0]));
    sort(all(op[1]));

    for(int j=0;j<2;j++)
    for(int i=1;i<sz(op[j]);i++)op[j][i]+=op[j][i-1];

    for(int i=0;i<=sz(op[0]);i++){
        int sum=(i?op[0][i-1]:0);
        int rem=k-sum;
        if(rem>=0){
            int cnt1=i;
            int cnt2= upper_bound(all(op[1]),rem)-op[1].begin();
            ans=min(ans,bad-cnt1-cnt2*2);
        }
        else break;
    }

    cout<<ans<<'\n';
}

void File() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}