#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define ll long long int
#define endl "\n"
#define pb push_back
#define mp make_pair
#define ut unsigned int
#define ss second
#define ff first
#define vi vector<int>
#define vl vector<ll>
#define lb lower_bound
#define up upper_bound
#define re return
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
int main()
{
int t ;
cin >> t;
while(t--)
{
ll n,k,cnt1=0,cnt0=0,f=0,i,a=0,b=0;
cin>>n>>k;
string s;
cin>>s;
vi v;
for(i=0;i<n;i++){
if(s[i]=='0'){
a++;
}
else
break;
}
for(i=n-1;i>=0;i--){
if(s[i]=='0'){
b++;
}
else
break;
}
for(i=0;i<n;i++){
if(s[i]=='0'){
cnt0++;
cnt1++;
}
else
{
v.pb(cnt0);
cnt0=0;
}
}
if(cnt0>0)
v.pb(cnt0);
sort(v.begin(),v.end());
ll r=v.size(),s1=0,flag=0,temp=0;;
for(i=0;i<r;i++)
s1=s1+v[i];
if(n==1)
cout<<"0";
else if(cnt1==n || cnt1==0)
cout<<"0";
else{
i=0;
while(k>0){
s1=s1-v[r-1-i];
if(k==1){
if(flag==1 && temp==1)
break;
else if(flag==0 && temp==0){
s1=s1+v[r-1-i];
s1=s1-max(a,b);
break;
}
else if(flag==0){
s1=s1+v[r-1-i];
s1=s1-a;
break;
}
else if(temp==0)
{
s1=s1+v[r-1-i];
s1=s1-b;
break;
}
}
else if(v[r-1-i]==a && flag==0){
k--;
flag=1;
}
else if(v[r-1-i]==b && temp==0){
k--;
temp=1;
}
else
k=k-2;
i++;
}
if(s1<0)
s1=0;
cout<<s1<<" ";
}
cout<<endl;
}
return 0;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKI2RlZmluZSBtb2QgMTAwMDAwMDAwNwojZGVmaW5lIGxsIGxvbmcgbG9uZyBpbnQKI2RlZmluZSBlbmRsICJcbiIKI2RlZmluZSBwYiBwdXNoX2JhY2sKI2RlZmluZSBtcCBtYWtlX3BhaXIKI2RlZmluZSB1dCB1bnNpZ25lZCBpbnQKI2RlZmluZSBzcyBzZWNvbmQKI2RlZmluZSBmZiBmaXJzdAojZGVmaW5lIHZpIHZlY3RvcjxpbnQ+CiNkZWZpbmUgdmwgdmVjdG9yPGxsPgojZGVmaW5lIGxiIGxvd2VyX2JvdW5kCiNkZWZpbmUgdXAgdXBwZXJfYm91bmQKI2RlZmluZSByZSByZXR1cm4gCiNkZWZpbmUgeWVzIGNvdXQ8PCJZRVMiPDxlbmRsCiNkZWZpbmUgbm8gY291dDw8Ik5PIjw8ZW5kbAoKCmludCBtYWluKCkKewppbnQgdCA7CmNpbiA+PiB0Owp3aGlsZSh0LS0pIAp7CiAgbGwgbixrLGNudDE9MCxjbnQwPTAsZj0wLGksYT0wLGI9MDsKICBjaW4+Pm4+Pms7CiAgc3RyaW5nIHM7CiAgY2luPj5zOwogIHZpIHY7CiAKICBmb3IoaT0wO2k8bjtpKyspewogIAlpZihzW2ldPT0nMCcpewogIAlhKys7CiAgCX0KICAJZWxzZQogIAlicmVhazsKICB9CiAgZm9yKGk9bi0xO2k+PTA7aS0tKXsKICAJaWYoc1tpXT09JzAnKXsKICAJYisrOwogICAgfQogIAllbHNlCiAgCWJyZWFrOwogIH0KCiAgZm9yKGk9MDtpPG47aSsrKXsKICAJaWYoc1tpXT09JzAnKXsKICAJY250MCsrOwogIAljbnQxKys7CiAgCX0KICAJZWxzZQogIAl7CiAgCQl2LnBiKGNudDApOwogIAkJY250MD0wOwogIAl9CiAgfQogIGlmKGNudDA+MCkKICB2LnBiKGNudDApOwogIHNvcnQodi5iZWdpbigpLHYuZW5kKCkpOwogIGxsIHI9di5zaXplKCksczE9MCxmbGFnPTAsdGVtcD0wOzsKICBmb3IoaT0wO2k8cjtpKyspCiAgczE9czErdltpXTsKICBpZihuPT0xKQogIGNvdXQ8PCIwIjsKICBlbHNlIGlmKGNudDE9PW4gfHwgY250MT09MCkKICBjb3V0PDwiMCI7CiAgZWxzZXsKICBpPTA7CiAgIHdoaWxlKGs+MCl7CiAgIAlzMT1zMS12W3ItMS1pXTsKICAgCWlmKGs9PTEpewogICAJCWlmKGZsYWc9PTEgJiYgdGVtcD09MSkKICAgCQlicmVhazsKICAgCQllbHNlIGlmKGZsYWc9PTAgJiYgdGVtcD09MCl7CiAgIAkJCXMxPXMxK3Zbci0xLWldOwogICAJCQlzMT1zMS1tYXgoYSxiKTsKICAgCQkJYnJlYWs7CiAgIAkJfQogICAJCWVsc2UgaWYoZmxhZz09MCl7CiAgIAkJCXMxPXMxK3Zbci0xLWldOwogICAJCQlzMT1zMS1hOwogICAJCQlicmVhazsKICAgCQl9CiAgIAkJZWxzZSBpZih0ZW1wPT0wKQogICAJCXsKICAgCQkJczE9czErdltyLTEtaV07CiAgIAkJCXMxPXMxLWI7CiAgIAkJCWJyZWFrOwogICAJCX0KICAgCX0KICAgCWVsc2UgaWYodltyLTEtaV09PWEgJiYgZmxhZz09MCl7CiAgIAkJay0tOwogICAJCWZsYWc9MTsKICAgCX0KICAgCWVsc2UgaWYodltyLTEtaV09PWIgJiYgdGVtcD09MCl7CiAgIAkJay0tOwogICAJCXRlbXA9MTsKICAgCX0KICAgCWVsc2UgCiAgIAlrPWstMjsKICAgCWkrKzsKICAgfQogICBpZihzMTwwKQogICBzMT0wOwogICBjb3V0PDxzMTw8IiAiOwogIH0KICBjb3V0PDxlbmRsOwp9ICAKcmV0dXJuIDA7Cn0=