#include <bits/stdc++.h>
using namespace std;
const int MN = 1000000;
int N, K, s[MN], dp[MN][2], psa[MN];
int query(int i, int j) {
  if (j < i)
    return 0;
  else if (i == 0)
    return psa[j];
  return psa[j] - psa[i - 1];
}
int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    char tmp[MN + 1];
    scanf("%d %d %s", &N, &K, tmp);
    N = strlen(tmp);
    for (int i = 0; i < N; i++) {
      s[i] = tmp[i] - '0';
    }
    psa[0] = s[0];
    for (int i = 1; i < N; i++) {
      psa[i] = psa[i - 1] + s[i];
    }
    for (int i = 0; i < N; i++) {
      for (int c = 0; c < 2; c++) {
        int st = c ? !s[i] : s[i];
        if (i == 0) {
        } else if (i - K < 0 || query(0, i - 1) == 0) {
          dp[i][c] =
              st == 1 ? query(0, i - 1) : min(dp[i - 1][0], dp[i - 1][1]);
        } else {
          if (st == 1) {
            dp[i][c] = query(i - K + 1, i - 1);
            if (s[i - K] == 1)
              dp[i][c] += dp[i - K][0];
            else
              dp[i][c] += dp[i - K][1];
          } else {
            dp[i][c] = min(dp[i - 1][0], dp[i - 1][1]);
          }
        }
        dp[i][c] += c;
        dp[i][c] = min(dp[i][c], query(0, i - 1));
      }
    }
    printf("%d\n", min(dp[N - 1][0], dp[N - 1][1]));
  }
  return 0;
}
