#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
using u64 = uint64_t;
using u128 = __uint128_t;
void solve() {
  int n, k;
  cin >> n >> k;
  string s;
  cin >> s;
  int tot = 0;
  for (auto& x : s) tot += (x == '1');
  int ans = tot;
  for (int i(0); i < k; ++i) {
    int x = 0, y = 0;
    for (int j(i); j < n; j += k) {
      if (s[j] == '1')
        x++;
      else
        y++;
      if (y <= x)
        ans = min(ans, tot - x + y);
      else
        x = 0, y = 0;
    }
  }
  cout << ans << '\n';
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int t;
  cin >> t;
  for (int i(1); i <= t; ++i) {
    solve();
  }
  cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s.\n";
  return 0;
}
