#include <bits/stdc++.h>
using namespace std;
const int N = 200000 + 10;
const int K = 200 + 10;
int n,k;
int T;
int id[K],minn[K],a[N];
int opt[N][K],w[N],b[N];
char ch;
int read(){
    char ch; int sum = 0,flag = 1;
    ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-') flag = -flag; ch = getchar();}
    while(ch >= '0' && ch <= '9'){sum = sum * 10 + ch - '0'; ch = getchar();}
    return sum * flag;
}
int main(){
    T = read();
    while(T--){
	    n = read();
	    k = read();
	    memset(opt,0,sizeof(opt));
	    memset(w,0,sizeof(w));
	    memset(b,0,sizeof(b));
	    memset(minn,0,sizeof(minn));
	    memset(id,0,sizeof(id));
	    for(int i = 1; i <= n; i++){
		    cin >> ch;
		    a[i] = (ch - '0');
		    w[i] = w[i - 1] + (a[i] == 0);
		    b[i] = b[i - 1] + (a[i] == 1);
		}
		for(int i = 1; i <= n; i++){
		    for(int j = 0; j <= k; j++){
			    opt[i][j] = opt[i - 1][j] + a[i];
			    if(j > 0)
			    opt[i][j] = min(opt[i][j],opt[id[j - 1]][j - 1] + w[i] - w[id[j - 1]]);
			    if(opt[i][j] - w[i] < minn[j]){
				    minn[j] = opt[i][j] - w[i];
				    id[j] = i;
				}
			}
		}
		printf("%d\n",opt[n][k]);
	}
	return 0;
}