#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 1000;
char a[maxn];
int sum[maxn];
int main() {
  int t;
  cin >> t;
  while (t--) {
    int n, k;
    cin >> n >> k;
    cin >> a + 1;
    for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + (a[i] == '1');
    int ans = 0x3f3f3f3f;
    for (int i = 1; i <= k; i++) {
      vector<int> v;
      for (int j = i; j <= n; j += k) {
        if (a[j] == '1')
          v.push_back(1);
        else
          v.push_back(-1);
      }
      int now = 0, mx = 0;
      for (int j = 0; j < v.size(); j++) {
        now += v[j];
        if (now < 0) now = 0;
        mx = max(now, mx);
      }
      ans = min(sum[n] - mx, ans);
    }
    cout << ans << '\n';
  }
}
