#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
const int INF = 0x3f3f3f3f;
const int inf = -INF;
const int mod = 1e9 + 7;
const double pi = acos(-1.0);
string s;
int pre[N];
int dp[N][2];
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int T;
  cin >> T;
  while (T--) {
    int n, k;
    cin >> n >> k;
    cin >> s;
    pre[0] = 0;
    for (int i = 0; i <= n; i++) {
      dp[i][0] = dp[i][1] = 0;
    }
    s = " " + s;
    for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] + s[i] - '0';
    for (int i = 1; i <= n; i++) {
      int t = max(0, i - k);
      dp[i][0] = min(dp[i - 1][0], dp[i - 1][1]) + (s[i] == '1');
      dp[i][1] =
          min(pre[i - 1], dp[t][1] + pre[i - 1] - pre[t]) + (s[i] == '0');
    }
    int ans = min(dp[n][0], dp[n][1]);
    cout << ans << endl;
  }
  return 0;
}
