#include <bits/stdc++.h>
using namespace std;
int sum[1000000 + 10];
int dp[1000000 + 10][3];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int T;
  cin >> T;
  while (T--) {
    int n, k;
    cin >> n >> k;
    int ans = n;
    string s;
    cin >> s;
    int len = s.size();
    for (int i = (0); i < (len); i++) {
      if (s[i] == '1') sum[i] = 1;
      if (i > 0) sum[i] += sum[i - 1];
    }
    for (int i = (0); i < (k); i++) {
      for (int j = i; j < len; j += k) {
        dp[j][0] = sum[min(len - 1, j + k - 1)];
        dp[j][2] = dp[j][0];
        int res = 0;
        if (s[j] != '1') res++;
        res += sum[min(len - 1, j + k - 1)] - sum[j];
        if (j >= k) {
          dp[j][1] = res + min(dp[j - k][0], dp[j - k][1]);
          dp[j][2] = min(dp[j][2], dp[j - k][1] + sum[min(len - 1, j + k - 1)] -
                                       sum[j - 1]);
          dp[j][2] = min(dp[j][2], dp[j - k][2] + sum[min(len - 1, j + k - 1)] -
                                       sum[j - 1]);
        } else {
          if (j > 0)
            dp[j][1] = res + sum[max(j - 1, 0)];
          else
            dp[j][1] = res;
          dp[j][2] = dp[j][0];
        }
        if (j + k >= len) {
          ans = min(ans, dp[j][0]);
          ans = min(ans, dp[j][1]);
          ans = min(dp[j][2], ans);
        }
      }
    }
    cout << ans << "\n";
    for (int i = (0); i < (len); i++) sum[i] = 0;
    for (int i = (0); i < (len); i++) {
      dp[i][0] = 0;
      dp[i][1] = 0;
      dp[i][2] = 0;
    }
  }
  return 0;
}
