#include <bits/stdc++.h>
using namespace std;
char s[1000500];
int ones[1000500], zeros[1000500], dp[1000500];
inline int solve(const vector<int> &vt) {
  int n = vt.size();
  int cnt = 0;
  for (int i = 0; i < n; i++) {
    if (!vt[i]) cnt++;
    zeros[i] = cnt;
  }
  cnt = 0;
  for (int i = n - 1; i >= 0; i--) {
    ones[i] = cnt;
    if (vt[i]) cnt++;
  }
  cnt = n;
  for (int i = n - 1; i >= 0; i--) {
    cnt = min(cnt, zeros[i] + ones[i]);
    dp[i] = cnt;
  }
  int ret = n;
  cnt = 0;
  dp[n] = n;
  for (int i = 0; i <= n; i++) {
    ret = min(ret, dp[i] + cnt);
    if (vt[i]) cnt++;
    if (!vt[i]) cnt--;
  }
  return ret;
}
int main() {
  int test;
  scanf("%d", &test);
  while (test--) {
    int n, k;
    scanf("%d %d", &n, &k);
    scanf("%s", s);
    int cnt = 0;
    for (int i = 0; i < n; i++) {
      if (s[i] == '1') cnt++;
    }
    int ans = n;
    for (int i = 0; i < k; i++) {
      int tem = 0;
      vector<int> vt;
      for (int j = i; j < n; j += k) {
        if (s[j] == '1') tem++;
        vt.push_back((int)s[j] - '0');
      }
      ans = min(ans, solve(vt) + cnt - tem);
    }
    printf("%d\n", ans);
    ;
  }
  return 0;
}
