#include <bits/stdc++.h>   using namespace std;   const double eps = 1e-8;   const int mod = 1e9 + 7;   const int N = 1e6 + 10;   const int inf = 1e9;   int t, n, k;   char s[N];   int cnt[N];   int a[N], b[N];   int main() {     ios::sync_with_stdio(false);     cin >> t;     while (t--) {       cin >> n >> k;       cin >> s + 1;       for (int i = 1; i <= n; i++) {         cnt[i] = cnt[i - 1];         if (s[i] ==  1 ) cnt[i]++;       }       int ans = inf;       for (int i = 1; i <= k; i++) {         int ret = 0, mn = inf, tp = inf, l = 0;         vector<int> q;         q.push_back(0);         for (int j = i; j <= n; j += k) {           int tmp = cnt[j - 1] - cnt[l];           ret += tmp;           q.push_back(cnt[j] - cnt[j - 1]);           l = j;         }         ret += cnt[n] - cnt[l];         int sz = q.size() - 1;         for (int i = 1; i <= sz; i++) {           a[i] = a[i - 1];           b[i] = b[i - 1];           if (q[i] == 1)             a[i]++;           else             b[i]++;         }         tp = a[sz];         for (int i = sz; i >= 1; i--) {           mn = min(mn, b[i] - a[i] + a[sz]);           tp = min(tp, a[i - 1] - b[i - 1] + mn);         }         ans = min(ans, ret + tp);       }       cout << ans <<   n ;     }     return 0;   }   