#include <bits/stdc++.h>
using namespace std;
long long power(long long a, long long n) {
  long long p = 1;
  while (n > 0) {
    if (n % 2) {
      p = p * a;
    }
    n >>= 1;
    a *= a;
  }
  return p;
}
long long power(long long a, long long n, long long mod) {
  long long p = 1;
  while (n > 0) {
    if (n % 2) {
      p = p * a;
      p %= mod;
    }
    n >>= 1;
    a *= a;
    a %= mod;
  }
  return p % mod;
}
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
long long lcm(long long a, long long b) { return (a * b) / gcd(a, b); }
const int MOD = 1000000007;
const int FMOD = 998244353;
const double eps = 1e-9;
const int N = 1e6 + 5;
char s[N];
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long t;
  cin >> t;
  while (t--) {
    long long n, k;
    cin >> n >> k >> s + 1;
    long long pref[n];
    memset(pref, 0, sizeof(pref));
    for (int i = 1; i <= n; i++) pref[i] = pref[i - 1] + s[i] - '0';
    long long dp[n + 1][2];
    memset(dp, 0, sizeof(dp));
    for (long long i = 1; i <= n; i++) {
      long long making_one = 0;
      making_one += dp[max(i - k, 0LL)][1];
      making_one += pref[i - 1] - pref[max(i - k, 0LL)] + (s[i] == '0');
      long long making_zero = min(dp[i - 1][0], dp[i - 1][1]) + (s[i] == '1');
      long long seting_all_prevoius_one_equal_to_zero = pref[i - 1];
      dp[i][1] = min(making_one, seting_all_prevoius_one_equal_to_zero);
      dp[i][0] = making_zero;
    }
    cout << min(dp[n][0], dp[n][1]) << "\n";
  }
  return 0;
}
