#include <bits/stdc++.h>
using namespace std;
int main() {
  int t, n, k;
  scanf("%d", &t);
  char s[1000005];
  while (t--) {
    scanf("%d%d", &n, &k);
    scanf("%s", s);
    int sum = 0;
    for (int i = 0; i < n; i++) sum += s[i] - '0';
    int ans = sum;
    for (int i = 0; i < k; i++) {
      int cnt = 0;
      for (int j = i; j < n; j += k) {
        cnt += s[j] == '1' ? -1 : 1;
        cnt = min(0, cnt);
        ans = min(ans, sum + cnt);
      }
    }
    printf("%d\n", ans);
  }
}
