#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 25;
int N, K;
string S;
int F[MAXN];
int sum[MAXN];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int T;
  cin >> T;
  F[0] = 0;
  while (T--) {
    cin >> N >> K;
    cin.ignore();
    cin >> S;
    S = " " + S;
    for (int i = 1; i <= N; i++) F[i] = 0;
    sum[0] = 0;
    for (int i = 1; i <= N; i++) {
      sum[i] = sum[i - 1];
      if (S[i] == '1') sum[i]++;
    }
    int ans = sum[N];
    for (int i = 1; i <= N; i++) {
      int cur = (S[i] == '0' ? 1 : 0);
      int vt = max(0, i - K);
      F[i] = sum[i - 1] + cur;
      F[i] = min(F[i], F[vt] + sum[i - 1] - sum[vt] + cur);
      ans = min(ans, F[i] + sum[N] - sum[i]);
    }
    cout << ans << "\n";
  }
}
