CF1353E.K-periodic Garland

You are given a garland consisting of $n$ lamps. States of the lamps are represented by the string $s$ of length $n$. The $i$-th character of the string $s_i$ equals '0' if the $i$-th lamp is turned off or '1' if the $i$-th lamp is turned on. You are also given a positive integer $k$.

In one move, you can choose one lamp and change its state (i.e. turn it on if it is turned off and vice versa).

The garland is called $k$-periodic if the distance between each pair of adjacent turned on lamps is exactly $k$. Consider the case $k=3$. Then garlands "00010010", "1001001", "00010" and "0" are good but garlands "00101001", "1000001" and "01001100" are not. Note that the garland is not cyclic, i.e. the first turned on lamp is not going after the last turned on lamp and vice versa.

Your task is to find the minimum number of moves you need to make to obtain $k$-periodic garland from the given one.

You have to answer $t$ independent test cases.

你被给定一个由 $n$ 盏灯组成的彩灯串。灯的状态由一个长度为 $n$ 的字符串 $s$ 表示。字符串 $s$ 的第 $i$ 个字符 $s_i$ 为 '0' 表示第 $i$ 盏灯关闭，为 '1' 表示第 $i$ 盏灯开启。同时，你还被给定一个正整数 $k$。

在一次操作中，你可以选择一盏灯并改变其状态（即：若灯关闭则开启，若灯开启则关闭）。

若每对相邻的开启灯之间的距离恰好为 $k$，则称该彩灯串是 $k$-周期的。考虑 $k = 3$ 的情况：此时彩灯串 "00010010"、"1001001"、"00010" 和 "0" 是合法的，但 "00101001"、"1000001" 和 "01001100" 不合法。注意：彩灯串不是环状的，即第一个开启的灯与最后一个开启的灯之间不构成相邻关系。

你的任务是求出：将给定彩灯串变为 $k$-周期彩灯串所需的最少操作次数。

你需要回答 $t$ 个相互独立的测试用例。

The first line of the input contains one integer $t$ ($1 \le t \le 25~ 000$) — the number of test cases. Then $t$ test cases follow.

The first line of the test case contains two integers $n$ and $k$ ($1 \le n \le 10^6; 1 \le k \le n$) — the length of $s$ and the required period. The second line of the test case contains the string $s$ consisting of $n$ characters '0' and '1'.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$ ($\sum n \le 10^6$).

输入的第一行包含一个整数 $t$（$1 \le t \le 25~000$），表示测试用例的数量。随后是 $t$ 个测试用例。

每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 10^6$；$1 \le k \le n$），分别表示字符串 $s$ 的长度以及所需的周期。每个测试用例的第二行包含一个由 $n$ 个字符 '0' 和 '1' 组成的字符串 $s$。

保证所有测试用例的 $n$ 之和不超过 $10^6$（即 $\sum n \le 10^6$）。

For each test case, print the answer — the minimum number of moves you need to make to obtain $k$-periodic garland from the given one.

对于每个测试用例，输出答案——即从给定的彩灯串得到 $k$-周期彩灯串所需的最少操作次数。