#include <bits/stdc++.h>
using namespace std;
string s;
int total;
vector<int> cnt;
int solve(int num, string s) {
  int n = s.size();
  int all = cnt[num];
  int ans = all;
  vector<int> res(n);
  int pref = 0;
  for (int i = 0; i < n; ++i) {
    int cur = s[i] - '0';
    pref += cur;
    res[i] = 1 - cur;
    if (i > 0) res[i] += min(res[i - 1], pref - cur);
    ans = min(ans, res[i] + all - pref);
  }
  return ans + total - cnt[num];
}
int main() {
  int t, i, n, m;
  scanf("%d", &t);
  while (t--) {
    total = 0;
    scanf("%d %d", &n, &m);
    vector<string> a(m);
    cnt.assign(m, 0);
    cin >> s;
    for (i = 0; i < n; ++i) {
      a[i % m] += s[i];
      if (s[i] == '1') {
        cnt[i % m]++;
        total++;
      }
    }
    int res = 10000000;
    for (i = 0; i < m; ++i) res = min(solve(i, a[i]), res);
    printf("%d\n", res);
  }
}
