#include <bits/stdc++.h>
using namespace std;
int dp1[1001000], dp2[1001000];
char str[1001000];
int pos[1001000];
int main() {
  int test;
  scanf("%d", &test);
  while (test--) {
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) dp1[i] = dp2[i] = 0;
    cin >> str + 1;
    int L = strlen(str + 1);
    int cnt = 0;
    for (int i = 1; i <= L; i++) {
      dp1[i] = dp2[i] = 0;
      if (str[i] == '1') pos[cnt++] = i;
    }
    for (int i = 1; i <= L; i++) {
      if (str[i] == '1') {
        dp1[i] = min(dp1[i - 1], dp2[i - 1]) + 1;
        if (i > k) {
          int t1 = upper_bound(pos, pos + cnt, i - k) - pos;
          int t2 = upper_bound(pos, pos + cnt, i - 1) - pos;
          int t3 = upper_bound(pos, pos + cnt, 0) - pos;
          dp2[i] = min(dp2[i - k], t1 - t3) + t2 - t1;
        } else {
          int t1 = upper_bound(pos, pos + cnt, 0) - pos;
          int t2 = upper_bound(pos, pos + cnt, i - 1) - pos;
          dp2[i] = t2 - t1;
        }
      } else {
        dp1[i] = min(dp1[i - 1], dp2[i - 1]);
        if (i > k) {
          int t1 = upper_bound(pos, pos + cnt, i - k) - pos;
          int t2 = upper_bound(pos, pos + cnt, i - 1) - pos;
          int t3 = upper_bound(pos, pos + cnt, 0) - pos;
          dp2[i] = 1 + min(dp2[i - k], t1 - t3);
          dp2[i] += t2 - t1;
        } else {
          int t1 = upper_bound(pos, pos + cnt, 0) - pos;
          int t2 = upper_bound(pos, pos + cnt, i - 1) - pos;
          dp2[i] = 1 + t2 - t1;
        }
      }
    }
    printf("%d\n", min(dp1[L], dp2[L]));
  }
  return 0;
}
