#include <bits/stdc++.h>
using namespace std;
using ll = long long;
string a;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int t;
  cin >> t;
  while (t--) {
    int n, k;
    cin >> n >> k >> a;
    int ans = 0, rmin = 0;
    for (int y = 0; y < k; y++) {
      int cs = 0, mf = 0, tans = 0, tval = 0;
      for (int i = 0; y + i * k < n; i++) {
        tans += a[y + i * k] == '1';
        cs += (a[y + i * k] == '1');
        tval = min(mf - (2 * cs - (i + 1)), tval);
        mf = min(mf, 2 * cs - (i + 1));
      }
      ans += tans;
      rmin = min(rmin, tval);
    }
    cout << ans + rmin << '\n';
  }
}
