#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int t, n, k;
string s;
int dp[N], pref[N];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> t;
  while (t--) {
    cin >> n >> k >> s;
    pref[0] = 0;
    for (int i = (1); i < (n + 1); i++) {
      pref[i] = pref[i - 1] + (s[i - 1] == '1');
    }
    int ans = pref[n];
    for (int i = (1); i < (n + 1); i++) {
      int L = max(0, i - k);
      dp[i] =
          (s[i - 1] == '0') + min(pref[i - 1], (pref[i - 1] - pref[L]) + dp[L]);
      ans = min(ans, pref[n] - pref[i] + dp[i]);
    }
    cout << ans << '\n';
  }
}
