#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<db, db>;
using vi = vector<int>;
using vl = vector<ll>;
using vd = vector<db>;
using vs = vector<string>;
using vii = vector<pii>;
using vll = vector<pll>;
using vdd = vector<pdd>;
template <class T>
bool ckmin(T& a, const T& b) {
  return (b < a) ? a = b, 1 : 0;
}
template <class T>
bool ckmax(T& a, const T& b) {
  return (a < b) ? a = b, 1 : 0;
}
const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const int kx[] = {0, 1, 0, -1}, ky[] = {1, 0, -1, 0};
void fileIO(string filename) {
  freopen((filename + ".in").c_str(), "r", stdin);
  freopen((filename + ".out").c_str(), "w", stdout);
}
int solve(string s) {
  int n = (int)s.size(), tot = count((s).begin(), (s).end(), '1'), cmin = tot,
      cur = 0;
  vi dp(n);
  for (int(i) = 0; i < n; ++i) {
    cur += s[i] == '1';
    dp[i] = s[i] == '0';
    if (i) dp[i] += min(dp[i - 1], cur - (s[i] == '1'));
    ckmin(cmin, dp[i] + tot - cur);
  }
  return cmin;
}
int main(void) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    int n, k, tot, ans = INT_MAX;
    cin >> n >> k;
    string ss;
    cin >> ss;
    tot = count((ss).begin(), (ss).end(), '1');
    vs s(k);
    vi cnt(k);
    for (int(i) = 0; i < n; ++i) s[i % k] += ss[i];
    for (int(i) = 0; i < k; ++i)
      cnt[i] = count((s[i]).begin(), (s[i]).end(), '1');
    for (int(i) = 0; i < k; ++i) ckmin(ans, solve(s[i]) + tot - cnt[i]);
    cout << ans << '\n';
  }
  cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
}
