#include<bits/stdc++.h>
using namespace std;
int n,k;
string a;
int pre[200005];
int dp[200005][205];
int o[205];
void solve(){
	cin>>n>>k;
	cin>>a;
	a=" "+a;
	for(int i=1;i<=n;i++)pre[i]=pre[i-1]+(a[i]=='1');
	for(int i=0;i<=n;i++){
		for(int j=0;j<=k;j++)dp[i][j]=(1<<30);
	}
	for(int i=0;i<=k;i++){
		o[i]=(1<<30);
	}
	o[0]=0;
	dp[0][0]=0;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=k;j++)dp[i][j]=dp[i-1][j]+(a[i]-'0');
		for(int j=1;j<=k;j++){
			dp[i][j]=min(dp[i][j],i-pre[i]+o[j-1]);
			/*
			for(int x=0;x<i;x++){
				dp[i][j]=min(dp[i][j],(i-pre[i])+dp[x][j-1]-x+pre[x]);
			}*/
		}
		if(i==n)continue;
		for(int j=0;j<=k;j++){
			o[j]=min(o[j],dp[i][j]-i+pre[i]);
		}
	}
	int res=1<<30;
	for(int i=0;i<=k;i++)res=min(res,dp[n][i]);
	cout<<res<<"\n";
}
signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	int t;
	cin>>t;
	while(t--)solve();
	return 0;
}