#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
const long long linf = 0x3f3f3f3f3f3f3f3f;
string A[1000100];
string S;
int cont[1000100];
int qnt;
int main() {
  int t;
  cin >> t;
  while (t--) {
    int n, k;
    cin >> n >> k;
    cin >> S;
    for (int i = 0; i < n; i++) {
      A[i % k].push_back(S[i]);
      if (S[i] == '1') cont[i % k]++, qnt++;
    }
    int ans = qnt;
    for (int i = 0; i < k; i++) {
      vector<int> pref, dp;
      pref.push_back(0);
      dp.push_back(0);
      for (int j = 0; j < A[i].size(); j++) {
        pref.push_back(pref[j] + (A[i][j] == '1' ? 1 : 0));
        dp.push_back(min(dp[j] + (A[i][j] == '1' ? 0 : 1),
                         pref[j] + (A[i][j] == '1' ? 0 : 1)));
      }
      int aux = pref[A[i].size()];
      for (int j = 0; j < A[i].size(); j++) {
        aux = min(aux, dp[j + 1] + pref[A[i].size()] - pref[j + 1]);
      }
      ans = min(ans, aux + qnt - pref[A[i].size()]);
    }
    cout << ans << "\n";
    qnt = 0;
    for (int i = 0; i < k; i++) cont[i] = 0, A[i].clear();
  }
  return 0;
}
