Let's focus on finding the minimum possible sum (maximum is similar).

We first note that if $b_i$ is fixed, then $b_{i+K}$ can be determined, since $b_{i+K}\equiv r_i+r_{i+1}+b_i\pmod 2$. So for each $1\le i\le K$, let's determine the minimum possible value of $b_i+b_{i+K}+\dots$ among the two candidate values (derived from $b_i=0$ and $b_i=1$, respectively), and add this value to the candidate answer. Let's also keep track of the parity of the number of ones among $b_{1\dots K}$ so far, and the minimum absolute difference between two candidate values seen so far.

Our candidate answer will certainly be a lower bound on the true answer. However, it might not actually be attainable since it might violate the constraint imposed by $r_1$. If the constraint is violated, we'll need to flip at least one of $b_{1\dots K}$ to satisfy the constraint. In this case, it is optimal to choose one $i$ with the minimum difference between the two candidate values to flip. This increases the candidate answer by that difference.

These observations allow us to solve each test in $O(N)$ time.

Python full solution:

def solve(N, K, r):
    min_sum = 0
    parity = 0  # parity of number of ones in first K elements of b
    min_dif = N

    for i in range(K):
        cand = [0]  # find one candidate sequence for b[i, i+K, i+2K, ...]
        for j in range(i + K, N, K):
            cand.append(cand[-1] ^ (ord(r[j - K]) - ord('0')) ^ (ord(r[j - K + 1]) - ord('0')))
        cand_sum0 = sum(cand)
        cand_sum1 = len(cand) - cand_sum0
        min_sum += min(cand_sum0, cand_sum1)
        if cand_sum1 < cand_sum0:
            parity ^= 1
        min_dif = min(min_dif, abs(cand_sum0 - cand_sum1))

    def get_min_sum():
        return min_sum + (parity != ord(r[0]) - ord('0')) * min_dif

    def get_max_sum():
        return N - min_sum - ((parity + K) & 1 != ord(r[0]) - ord('0')) * min_dif

    print(get_min_sum(), get_max_sum())


def main():
    T = int(input())
    for _ in range(T):
        N, K = map(int, input().split())
        r = input()
        solve(N, K, r)


if __name__ == "__main__":
    main()