#include <bits/stdc++.h>
using namespace std;
void Ios() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  return;
}
constexpr int kN = int(1E6 + 10);
int s1[kN], dp[kN];
void solve() {
  int n, k, ans;
  string s;
  cin >> n >> k >> s;
  for (int i = 1; i <= n; i++) s1[i] = (s[i - 1] == '1' ? 1 : 0);
  for (int i = 1; i <= n; i++) s1[i] += s1[i - 1];
  for (int i = 1; i <= k; i++) {
    if (s[i - 1] == '1')
      dp[i] = s1[i - 1];
    else
      dp[i] = s1[i - 1] + 1;
  }
  for (int i = k + 1; i <= n; i++) {
    if (s[i - 1] == '1')
      dp[i] = min(s1[i - 1], dp[i - k] + s1[i - 1] - s1[i - k]);
    else
      dp[i] = min(s1[i - 1], dp[i - k] + s1[i - 1] - s1[i - k]) + 1;
  }
  ans = s1[n];
  for (int i = 1; i <= n; i++) ans = min(ans, dp[i] + (s1[n] - s1[i]));
  printf("%d\n", ans);
  return;
}
int main() {
  Ios();
  int t;
  cin >> t;
  for (int i = 1; i <= t; i++) {
    solve();
  }
}
