K-периодичная гирлянда

// OK E_div3_642 https://codeforces.com/contest/1353/problem/E

#include <iostream>

int main() {
    std::ios_base::sync_with_stdio(false);
    size_t t;
    std::cin >> t;
    while (t-- > 0) {
        size_t n, k;
        std::cin >> n >> k;
        std::string s;
        std::cin >> s;
        size_t all = 0;
        for (auto ch : s) {
            all += (ch == '1');
        }
        size_t res = all;
        for (size_t i = 0; i < k; i++) {
            size_t cur = all;
            int32_t start = i;
            while (start + k < n) {
                start += k;
            }
            for (int32_t j = start; j >= 0; j -= k) {
                cur = std::min(cur - (s[j] == '1') + (s[j] == '0'), all + (s[j] == '0') - (s[j] == '1'));
                res = std::min(cur, res);
            }
        }
        std::cout << res << '\n';
    }
    return 0;
}