#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long t;
  cin >> t;
  while (t--) {
    long long n, k;
    cin >> n;
    cin >> k;
    string s;
    cin >> s;
    vector<vector<long long> > arr(n, vector<long long>(2));
    vector<long long> cnt(n);
    for (long long i = 0; i < n; i++) {
      if (i == 0) {
        if (s[i] == '1') cnt[i] = 1;
        continue;
      }
      cnt[i] = cnt[i - 1];
      cnt[i] += (s[i] == '1');
    }
    for (long long i = 0; i < n; i++) {
      if (i == 0) {
        arr[i][0] = (s[i] == '1');
        arr[i][1] = (s[i] == '0');
        continue;
      }
      if (s[i] == '0') {
        arr[i][0] = min(arr[i - 1][0], arr[i - 1][1]);
        long long a = cnt[i - 1];
        long long b = arr[max(i - k, 0ll)][1] + cnt[i - 1];
        if (i >= k) b -= cnt[i - k];
        arr[i][1] = min(a, b) + 1;
      } else {
        arr[i][0] = min(arr[i - 1][0], arr[i - 1][1]) + 1;
        long long a = cnt[i - 1];
        long long b = arr[max(i - k, 0ll)][1] + cnt[i - 1];
        if (i >= k) b -= cnt[i - k];
        arr[i][1] = min(a, b);
      }
    }
    cout << min(arr[n - 1][0], arr[n - 1][1]) << endl;
  }
  return 0;
}
