#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define fri(i,a,b) for(ll i=a;i<b;i++)
#define tc ll t;cin>>t;while(t--)
typedef pair<ll, ll> ii;
typedef vector<ii> vii;
int main() {
ios_base::sync_with_stdio(false);cin.tie(NULL);
tc{
ll n,k;cin>>n>>k;
string s;cin>>s;
if(n==0 || n==1)cout<<0<<endl;
else{
vii v;
ll zt=0;
ll z=0;
fri(i,0,n){
if(s[i]=='0'){
z++;
}
else{
if(z!=0){
zt+=z;
if(i-z==0){
v.pb(mp(z,1LL));
}
else{
v.pb(mp(z,2LL));
}
z=0;
}
}
}
if(z!=0){v.pb(mp(z,1LL));zt+=z;}
ll c=0;
sort(v.rbegin(),v.rend());
// fri(i,0,v.size()){
// cout<<v[i].ff<<" "<<v[i].ss<<endl;
// }
fri(i,0,v.size()){
if(v[i].ss <=k){
c+= v[i].ff;
k-=v[i].ss;
// cout<<k<<endl;
}
}
// cout<<zt<<" "<<c<<endl;
cout<<zt-c<<endl;
}
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiAgCiNkZWZpbmUgbGwgbG9uZyBsb25nCiNkZWZpbmUgcGIgcHVzaF9iYWNrCiNkZWZpbmUgbXAgbWFrZV9wYWlyCiNkZWZpbmUgZmYgZmlyc3QKI2RlZmluZSBzcyBzZWNvbmQKI2RlZmluZSBmcmkoaSxhLGIpIGZvcihsbCBpPWE7aTxiO2krKykKI2RlZmluZSB0YyBsbCB0O2Npbj4+dDt3aGlsZSh0LS0pCnR5cGVkZWYgcGFpcjxsbCwgbGw+IGlpOwp0eXBlZGVmIHZlY3RvcjxpaT4gdmlpOwoKaW50IG1haW4oKSB7Cglpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTtjaW4udGllKE5VTEwpOwp0Y3sKICAgIGxsIG4saztjaW4+Pm4+Pms7CiAgICBzdHJpbmcgcztjaW4+PnM7CiAgICBpZihuPT0wIHx8IG49PTEpY291dDw8MDw8ZW5kbDsKICAgIGVsc2V7CiAgICAgICAgdmlpIHY7CiAgICAgICAgbGwgenQ9MDsKICAgICAgICBsbCB6PTA7CiAgICAgICAgZnJpKGksMCxuKXsKICAgICAgICAgICAgaWYoc1tpXT09JzAnKXsKICAgICAgICAgICAgICAgIHorKzsKICAgICAgICAgICAgfQogICAgICAgICAgICBlbHNlewogICAgICAgICAgICAgICAgaWYoeiE9MCl7CiAgICAgICAgICAgICAgICAgICAgenQrPXo7CiAgICAgICAgICAgICAgICAgICAgaWYoaS16PT0wKXsKICAgICAgICAgICAgICAgICAgICAgICAgdi5wYihtcCh6LDFMTCkpOwogICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAgICBlbHNlewogICAgICAgICAgICAgICAgICAgICAgICB2LnBiKG1wKHosMkxMKSk7CiAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgIHo9MDsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICBpZih6IT0wKXt2LnBiKG1wKHosMUxMKSk7enQrPXo7fQogICAgICAgIGxsIGM9MDsKICAgICAgICBzb3J0KHYucmJlZ2luKCksdi5yZW5kKCkpOwogICAgICAgIAogICAgICAgIC8vIGZyaShpLDAsdi5zaXplKCkpewogICAgICAgIC8vICAgICBjb3V0PDx2W2ldLmZmPDwiICI8PHZbaV0uc3M8PGVuZGw7CiAgICAgICAgLy8gfQogICAgICAgIAogICAgICAgIAogICAgICAgIGZyaShpLDAsdi5zaXplKCkpewogICAgICAgICAgICBpZih2W2ldLnNzIDw9ayl7CiAgICAgICAgICAgICAgICBjKz0gdltpXS5mZjsKICAgICAgICAgICAgICAgIGstPXZbaV0uc3M7CiAgICAgICAgICAgICAgICAvLyBjb3V0PDxrPDxlbmRsOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIC8vIGNvdXQ8PHp0PDwiICI8PGM8PGVuZGw7CiAgICAgICAgY291dDw8enQtYzw8ZW5kbDsKICAgIH0KICAgIAp9ICAgCgoJcmV0dXJuIDA7Cn0K