#include <bits/stdc++.h>
using namespace std;
int t,n,k,f[210][200010],sum[200010];
string s;

struct node{
	int x,num;
	node(int xx, int numm) {
		x=xx,num=numm;
	}
	bool operator < (const node &a) const{
		return num < a.num;
	}
};

int main(){
	cin >> t;
	while(t--) {
		cin >> n >> k >> s;
		
		while(k--) {
			int ans=0,l=0,r=0;
			priority_queue <node> q;
			q.push(node(-1,0));
			for(int i = 0; i < s.size(); i++) {
				sum[i] = sum[i-1]+(s[i]=='0'?1:-1);
				if(!q.empty()){
					if(sum[i]-q.top().num<ans){
						ans=sum[i]-q.top().num;
						l=q.top().x,r=i;
					}
				}
				q.push(node(i,sum[i]));
				//cout << q.top().num << " ";
			}
			for(int i = l+1; i <= r; i++) {
				if(s[i]=='0')s[i]='1';
				else s[i]='0';
			}
			//cout << s <<endl;
		}
		int ans=0;
		for(int i = 0; i < s.size(); i++) {
			ans+=(s[i]-'0');
		}
		cout << ans << endl;
	}
	return 0;
}