#include <bits/stdc++.h>
using namespace std;
int main() {
  int t;
  cin >> t;
  while (t--) {
    int n, k;
    cin >> n >> k;
    int dp[n + 1], pre[n + 1];
    memset(dp, 0, sizeof(dp));
    string s;
    cin >> s;
    pre[0] = s[0] - '0';
    for (int i = 1; i < n; i++) pre[i] = pre[i - 1] + s[i] - '0';
    for (int i = n - 1; i >= 0; i--) {
      if (i + k >= n) {
        dp[i] = pre[n - 1] - pre[i];
      } else {
        if (s[i] == '1')
          dp[i] = min(dp[i + k] + pre[i + k - 1] - pre[i], pre[n - 1] - pre[i]);
        else
          dp[i] =
              min(dp[i + k] + pre[i + k - 1] - pre[i] + 1, pre[n - 1] - pre[i]);
      }
    }
    int ans = dp[0];
    for (int i = 1; i < n; i++) {
      dp[i] += pre[i - 1];
      ans = min(ans, dp[i]);
    }
    cout << ans << "\n";
  }
  return 0;
}
