#include<bits/stdc++.h>
using namespace std;
using ll = long long;
//using LL = __int128
ll n, k, a[222222], sum[222222], t, dp[2][222], g[222], h[222];
void debug(int x){
	cout << x << ": ";
	for(int i = 0 ; i <= k ; i++)
		cout << dp[x & 1][i] << " \n"[i == k];
}
int main(){
	scanf("%lld", &t);
	while(t--){
		scanf("%lld%lld", &n, &k);
		for(int i = 1 ; i <= n ; i++){
		scanf("%1lld", &a[i]);
			sum[i] = a[i] + sum[i - 1];
		}
		memset(g, 0x3f, sizeof g);
		memset(h, 0x3f, sizeof h);
		g[0] = h[0] = 0;
		for(ll i = 1 ; i <= n ; i++){
			dp[i & 1][0] = sum[i];
			g[0] = min(g[0], dp[i & 1][0] + sum[i] - i);
			h[0] = min(h[0], dp[i & 1][0] - sum[i]);
			for(int j = 1 ; j <= min(k, i) ; j++){
				//dp[i & 1][j] = LONG_LONG_MAX;
				dp[i & 1][j] = min(h[j] + sum[i], g[j - 1] - sum[i] + i);
				g[j] = min(g[j], dp[i & 1][j] + sum[i] - i);
				h[j] = min(h[j], dp[i & 1][j] - sum[i]);
			}
			//debug(i);
		}
		ll ans = LONG_LONG_MAX;
		for(int i = 0 ; i <= k ; i++)
			ans = min(ans, dp[n & 1][i]);
		printf("%lld\n", ans);
	}
	return 0;
}