#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
char str[N];
int sum[N], a[N], f[N];
void solve() {
  int n, k;
  scanf("%d%d%s", &n, &k, str + 1);
  int cnt = 0;
  for (int i = 1; i <= n; i++) {
    if (str[i] == '1') cnt++;
  }
  int res = inf;
  for (int i = 1; i <= k; i++) {
    int p = i, idx = 0, first = 0;
    while (p <= n) {
      a[++idx] = str[p] - '0';
      if (str[p] == '1') first++;
      p += k;
    }
    int ans = cnt - first;
    multiset<int> s;
    for (int j = 1; j <= idx; j++) {
      sum[j] = sum[j - 1];
      if (a[j] == 1) sum[j]++;
      f[j] = j - 2 * sum[j];
      s.insert(f[j]);
    }
    int mx = sum[idx] + *(s.begin());
    for (int j = 1; j < idx; j++) {
      s.erase(s.find(f[j]));
      auto it = s.begin();
      int first = *it;
      mx = min(mx, -f[j] + sum[idx] + first);
    }
    mx = min(mx, sum[idx]);
    res = min(res, ans + mx);
  }
  printf("%d\n", res);
}
int main() {
  int t;
  cin >> t;
  while (t--) solve();
  return 0;
}
