#include <bits/stdc++.h>
using namespace std;
int DC(string s) {
  s = "0" + s;
  int ones = count(s.begin(), s.end(), '1');
  int ans = ones;
  vector<int> pro;
  int n = s.length();
  int x = 0;
  while (x < n) {
    int c = 0;
    while (x < n && s[x] == '0') {
      c++;
      x++;
    }
    pro.push_back(c);
    c = 0;
    while (x < n && s[x] == '1') {
      c++;
      x++;
    }
    pro.push_back(c);
  }
  if ((int)pro.size() == 1) return 0;
  int cur = pro[1];
  vector<int> cal((int)pro.size(), 0);
  vector<int> proc((int)pro.size(), 0);
  proc[1] = pro[1];
  cal[1] = 0;
  for (int i = 3; i < (int)pro.size(); i += 2) {
    cal[i] = min(pro[i - 1] + cal[i - 2], cur);
    cur += pro[i];
    proc[i] = cur;
  }
  for (int x = 1; x < (int)pro.size(); x += 2) {
    ans = min(ans, cal[x] + ones - proc[x]);
  }
  return ans;
}
int n, k;
string s;
void solve() {
  cin >> n >> k >> s;
  int ones = count(s.begin(), s.end(), '1');
  int ans = ones;
  for (int x = 0; x < k; x++) {
    string cur = "";
    for (int y = x; y < n; y += k) {
      cur += s[y];
    }
    int o = count(cur.begin(), cur.end(), '1');
    int res = DC(cur);
    ans = min(ans, res + ones - o);
  }
  cout << ans << endl;
}
int t;
int main() {
  cin >> t;
  while (t--) solve();
}
