#include <bits/stdc++.h>
using namespace std;
int maxSubArraySum(vector<long long> &a) {
  int size = a.size();
  int max_so_far = INT_MIN, max_ending_here = 0;
  for (int i = 0; i < size; i++) {
    max_ending_here = max_ending_here + a[i];
    if (max_so_far < max_ending_here) max_so_far = max_ending_here;
    if (max_ending_here < 0) max_ending_here = 0;
  }
  return max_so_far;
}
int main() {
  ios_base ::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long n, i, t, k;
  string s;
  cin >> t;
  while (t--) {
    cin >> n >> k >> s;
    vector<long long> a[k];
    long long cnt = 0;
    for (i = 0; i < k; i++) {
      for (long long j = i; j < n; j += k) {
        a[i].push_back((s[j] == '0' ? -1 : 1));
        cnt += (s[j] - '0');
      }
    }
    if (cnt < 2) {
      cout << "0\n";
      continue;
    }
    long long ans = 0;
    for (i = 0; i < k; i++) {
      ans = max(ans, (long long)maxSubArraySum(a[i]));
    }
    cout << min(cnt - ans, cnt - 1) << '\n';
  }
  return 0;
}
