#include <bits/stdc++.h>
using namespace std;
int main() {
  int t;
  cin >> t;
  for (int test = 0; test < t; test++) {
    int n, k;
    scanf("%d %d", &n, &k);
    string s;
    cin >> s;
    int ans = 0;
    int count_1 = 0;
    for (int i = 0; i < k; i++) {
      int longest_segment = 0;
      int ending_here = 0;
      for (int j = i; j < n; j += k) {
        if (s[j] == '1') {
          ending_here += 1;
          count_1++;
        } else {
          ending_here = max(0, ending_here - 1);
        }
        longest_segment = max(longest_segment, ending_here);
      }
      ans = max(ans, longest_segment);
    }
    ans = count_1 - ans;
    cout << ans << endl;
  }
}
