#include <bits/stdc++.h>
using namespace std;
long long dp[1000006], sum[1000006], d[1000006];
char s[1000006];
int main() {
  int T;
  cin >> T;
  while (T--) {
    int n, k;
    scanf("%d%d", &n, &k);
    scanf("%s", s + 1);
    int cnt = 0, flag = 1;
    for (int i = 1; i <= n; i++) sum[i] = 0;
    for (int i = 1; i <= n; i++) {
      if (s[i] == '1') sum[i] += 1, flag = 0;
      sum[i] += sum[i - 1];
    }
    if (n == 1 || flag) {
      puts("0");
      continue;
    }
    long long ans = 1e10;
    for (int i = 1; i <= n; i++) {
      if (i - k >= 0)
        dp[i] = min(dp[i - k] + sum[i - 1] - sum[i - k] + (s[i] == '1' ? 0 : 1),
                    sum[i - 1]);
      else
        dp[i] = sum[i - 1] + (s[i] == '1' ? 0 : 1);
      d[i] = dp[i] + sum[n] - sum[i];
      ans = min(ans, d[i]);
    }
    cout << ans << '\n';
  }
  return 0;
}
