#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int t, n, k;
int pre[N], f[N], g[N];
string s;
int main() {
  int i, ans, x;
  cin >> t;
  while (t--) {
    cin >> n >> k >> s;
    for (i = 0; i < n; i++) pre[i + 1] = pre[i] + s[i] - '0';
    if (pre[n] == 0) {
      printf("0\n");
      continue;
    }
    for (i = 1; i <= n; i++) {
      f[i] = pre[i - 1];
      if (i - k > 0) f[i] = min(f[i], f[i - k] + pre[i - 1] - pre[i - k]);
      if (s[i - 1] == '0') f[i]++;
    }
    for (i = n; i >= 1; i--) {
      g[i] = pre[n] - pre[i];
      if (i + k <= n) g[i] = min(g[i], g[i + k] + pre[i + k] - pre[i]);
      if (s[i - 1] == '0') g[i]++;
    }
    ans = n;
    for (i = 1; i <= n; i++) {
      x = f[i] + g[i];
      if (s[i - 1] == '0') x--;
      if (x < ans) ans = x;
    }
    printf("%d\n", ans);
  }
  return 0;
}
