#include <bits/stdc++.h>
using namespace std;
long long T, n, k, c[2], allones, ans, cur, best, sum[1000002];
string s;
vector<long long> f[1000002];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> T;
  while (T--) {
    ans = 1e9;
    allones = 0;
    cin >> n >> k >> s;
    for (long long i = 0; i < k + 1; i++) f[i].clear();
    for (long long i = 0; i < n; i++) allones += s[i] - '0';
    for (long long i = 0; i < k; i++) {
      c[0] = c[1] = 0;
      c[s[i] - '0'] = 1;
      for (long long j = i + k; j < n; j += k) {
        if (s[j] != s[j - k]) {
          if (c[1])
            f[i].push_back(c[1]);
          else if (!f[i].empty())
            f[i].push_back(-c[0]);
          c[0] = c[1] = 0;
          c[s[j] - '0'] = 1;
        } else
          c[s[j] - '0']++;
      }
      if (c[1]) f[i].push_back(c[1]);
    }
    for (long long i = 0; i < k; i++) {
      if (f[i].empty()) {
        ans = min(ans, allones);
        continue;
      }
      c[0] = c[1] = 0;
      for (auto it : f[i]) {
        if (it < 0)
          c[0] -= it;
        else
          c[1] += it;
      }
      sum[0] = 0;
      cur = f[i][0];
      for (long long j = 2; j < (long long)f[i].size(); j += 2) {
        sum[j] = min(cur, sum[j - 2] - f[i][j - 1]);
        cur += f[i][j];
      }
      best = 0;
      cur = f[i].back();
      ans = min(ans, allones - c[1] + sum[(long long)f[i].size() - 1]);
      for (long long j = (long long)f[i].size() - 3; j > -1; j -= 2) {
        best = min(cur, best - f[i][j + 1]);
        cur += f[i][j];
        ans = min(ans, allones - c[1] + best + sum[j]);
      }
    }
    cout << ans << "\n";
  }
  return 0;
}
