#include <bits/stdc++.h>
using namespace std;
char s[1000010];
int sum[1000010], dp[1000010];
int main() {
  int t, n, k, i, ans;
  scanf("%d", &t);
  while (t--) {
    scanf("%d%d%s", &n, &k, s + 1);
    for (i = 1; i <= n; i++) sum[i] = sum[i - 1] + s[i] - '0';
    for (i = 1; i <= n; i++) dp[i] = sum[i - 1] + (s[i] == '0');
    for (i = k + 1; i <= n; i++)
      dp[i] = min(dp[i], dp[i - k] + sum[i - 1] - sum[i - k] + (s[i] == '0'));
    ans = sum[n];
    for (i = 1; i <= n; i++) ans = min(ans, dp[i] + sum[n] - sum[i]);
    printf("%d\n", ans);
  }
  return 0;
}
