#include <bits/stdc++.h>
using namespace std;
int dp[1000100][2], cnt[1000100];
char s[1000100];
int main() {
  int t;
  cin >> t;
  while (t--) {
    int n, k;
    scanf("%d %d", &n, &k);
    scanf("%s", (s + 1));
    for (int i = 1; i <= n; i++)
      for (int j = 0; j < 2; j++) dp[i][j] = 1000000000;
    for (int i = 1; i <= n; i++) cnt[i] = cnt[i - 1] + (s[i] - '0');
    for (int i = 1; i <= n; i++) {
      for (int j = 0; j < 2; j++) {
        if (j == 0) {
          dp[i][j] = min(dp[i][j], dp[i - 1][0]);
          dp[i][j] = min(dp[i][j], dp[i - 1][1]);
        } else {
          dp[i][j] = min(dp[i][j], cnt[i - 1]);
          dp[i][j] = min(
              dp[i][j], cnt[i - 1] - cnt[max(0, i - k)] + dp[max(0, i - k)][1]);
        }
        if (s[i] - '0' != j) dp[i][j]++;
      }
    }
    int ans = min(dp[n][0], dp[n][1]);
    printf("%d\n", ans);
  }
  return 0;
}
