#include <bits/stdc++.h>
using namespace std;
int t;
int n, k;
string s;
int pref[1000005];
int dp[1000005];
int get(int a, int b) {
  if (b < a) return 0;
  return pref[b] - pref[a - 1];
}
int main() {
  cin >> t;
  while (t--) {
    cin >> n >> k;
    cin >> s;
    s = '?' + s;
    for (int i = 1; i <= n; i++) {
      pref[i] = pref[i - 1] + (s[i] == '1');
    }
    int ans = get(1, n);
    for (int i = 1; i <= n; i++) {
      int c1 = get(1, i - 1) + (s[i] != '1');
      int c2 = (i - k >= 1 ? dp[i - k] + get(i - k + 1, i - 1) + (s[i] != '1')
                           : 1 << 29);
      dp[i] = min(c1, c2);
      ans = min(ans, dp[i] + get(i + 1, n));
    }
    cout << ans << '\n';
  }
}
