#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-8;
const int mod = 1e9 + 7;
const int N = 1e6 + 10;
const int inf = 1e9;
int t, n, k;
char s[N];
int cnt[N];
int a[N], b[N];
int main() {
  ios::sync_with_stdio(false);
  cin >> t;
  while (t--) {
    cin >> n >> k;
    cin >> s + 1;
    for (int i = 1; i <= n; i++) {
      cnt[i] = cnt[i - 1];
      if (s[i] == '1') cnt[i]++;
    }
    int ans = inf;
    for (int i = 1; i <= k; i++) {
      int ret = 0, mn = inf, tp = inf, l = 0;
      vector<int> q;
      q.push_back(0);
      for (int j = i; j <= n; j += k) {
        int tmp = cnt[j - 1] - cnt[l];
        ret += tmp;
        q.push_back(cnt[j] - cnt[j - 1]);
        l = j;
      }
      ret += cnt[n] - cnt[l];
      int sz = q.size() - 1;
      for (int i = 1; i <= sz; i++) {
        a[i] = a[i - 1];
        b[i] = b[i - 1];
        if (q[i] == 1)
          a[i]++;
        else
          b[i]++;
      }
      tp = a[sz];
      for (int i = sz; i >= 1; i--) {
        mn = min(mn, b[i] - a[i] + a[sz]);
        tp = min(tp, a[i - 1] - b[i - 1] + mn);
      }
      ans = min(ans, ret + tp);
    }
    cout << ans << '\n';
  }
  return 0;
}
