#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &val) {
  val = 0;
  char c = getchar();
  int f = 1;
  while (!isdigit(c)) {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (isdigit(c)) {
    val = (val << 3) + (val << 1) + (c ^ 48);
    c = getchar();
  }
  val *= f;
}
template <typename T>
void write_(T val) {
  if (!val) return;
  write_(val / 10);
  putchar(val % 10 + 48);
}
template <typename T>
inline void write(T val) {
  if (val == 0)
    putchar(48);
  else if (val < 0) {
    putchar('-');
    write_(-val);
  } else
    write_(val);
}
const int N = 1e6 + 5;
string s, t[N];
int n, k, ans, res[N];
int solve(string str) {
  int all = count(str.begin(), str.end(), '1');
  int pre = 0, ret = all;
  for (register int i = 0; i < str.size(); i++) {
    int cur = str[i] == '1';
    pre += cur;
    res[i] = 1 - cur;
    if (i > 0) res[i] += min(res[i - 1], pre - cur);
    ret = min(ret, res[i] + all - pre);
  }
  return ret;
}
int main() {
  ios::sync_with_stdio(false);
  int test;
  cin >> test;
  while (test--) {
    cin >> n >> k >> s;
    for (register int i = 0; i < k; i++) t[i].clear();
    for (register int i = 0; i < s.size(); i++) t[i % k] += s[i];
    int all;
    ans = all = count(s.begin(), s.end(), '1');
    for (register int i = 0; i < k; i++)
      ans = min(ans,
                solve(t[i]) + all - (int)count(t[i].begin(), t[i].end(), '1'));
    cout << ans << endl;
  }
  return 0;
}
