#include <bits/stdc++.h>
using namespace std;
const long long LINF = 1E18;
const int INF = 1E9;
const int MOD = 1E9 + 7;
const int nmax = 5E6 + 5;
int t = 1;
int n, m, a[nmax], k, F[nmax], Sum[nmax];
void INPUT() { cin >> t; }
void SOLVE() {
  cin >> n >> k;
  string s;
  cin >> s;
  for (int i = 1; i <= n; i++) a[i] = s[i - 1] - '0';
  for (int i = 1; i <= n; i++) Sum[i] = Sum[i - 1] + a[i];
  for (int i = 1; i <= k; i++) {
    F[i] = (a[i] ^ 1) + Sum[i - 1];
  }
  for (int i = k + 1; i <= n; i++) {
    F[i] = Sum[i - 1] + (a[i] ^ 1);
    int Pre = i - k;
    if (Pre <= 0) continue;
    if (a[i] == 0) {
      F[i] = min(F[i], F[Pre] + 1 + Sum[i - 1] - Sum[Pre]);
    } else
      F[i] = min(F[i], F[Pre] + Sum[i - 1] - Sum[Pre]);
  }
  int res = Sum[n];
  for (int i = 1; i <= n; i++) {
    res = min(res, F[i] + Sum[n] - Sum[i]);
  }
  cout << res << endl;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  if (fopen("test"
            ".inp",
            "r")) {
    freopen(
        "test"
        ".inp",
        "r", stdin);
    freopen(
        "test"
        ".out",
        "w", stdout);
  }
  INPUT();
  while (t--) SOLVE();
  return 0;
}
