#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b) {
  for (; b; a %= b, swap(a, b))
    ;
  return a;
}
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  int t;
  cin >> t;
  while (t--) {
    int n, k;
    cin >> n >> k;
    int ones = 0;
    vector<int> one(k);
    string st;
    cin >> st;
    for (int i = 0; i < n; i++) {
      if (st[i] == '1') {
        one[i % k]++;
        ones++;
      }
    }
    int ans = ones;
    for (int i = 0; i < k; i++) {
      int tmp = ones - one[i % k];
      string t = "";
      vector<int> cnt;
      cnt.push_back(0);
      for (int j = i; j < n; j += k) {
        t += st[j];
        if (cnt.size() == 0)
          cnt.push_back(st[j] - '0');
        else
          cnt.push_back(cnt.back() + st[j] - '0');
      }
      int len = t.size();
      vector<int> dp(len + 1);
      int res = 1e9;
      for (int j = 1; j <= len; j++) {
        int p = (t[j - 1] == '0' ? 1 : 0);
        dp[j] = min(dp[j - 1] + p, cnt[j - 1] + p);
      }
      for (int j = 1; j <= len; j++) res = min(res, dp[j] + cnt[len] - cnt[j]);
      ans = min(ans, res + tmp);
    }
    cout << ans << "\n";
  }
}
