← 返回题目列表

Codeforces · 1353/E

E. K-周期花环

中文机器翻译题面 查看原题

你会得到一个由 $$$n$$$ 灯组成的花环。灯的状态由长度为 $$$n$$$ 的字符串 $$$s$$$ 表示。如果第 $$$i$$$ 个灯关闭,则字符串 $$$s_i$$$ 的第 $$$i$$$ 个字符等于“0”;如果第 $$$i$$$ 个灯打开,则该字符串的第 $$$i$$$ 个字符等于“1”。您还将获得一个正整数 $$$k$$$。

一步操作中,您可以选择一盏灯并更改其状态(即,如果关闭则将其打开,反之亦然)。

如果每对相邻打开的灯之间的距离恰好为 $$$k$$$,则该花环被称为 $$$k$$$-周期性的。考虑 $$$k=3$$$ 的情况。那么花环“00010010”、“1001001”、“00010”和“0”是好的,但花环“00101001”、“1000001”和“01001100”则不好。请注意,花环不是循环的,即第一个打开的灯不会在最后一个打开的灯之后熄灭,反之亦然。

你的任务是找到从给定的花环中获得 $$$k$$$-周期性花环所需的最少移动次数。

您必须回答 $$$t$$$ 独立测试用例。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 25~ 000$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。

测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 10^6; 1 \le k \le n$$$) — $$$s$$$ 的长度和所需的周期。测试用例的第二行包含字符串 $$$s$$$,由 $$$n$$$ 字符“0”和“1”组成。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^6$$$ ($$$\sum n \le 10^6$$$)。

输出

对于每个测试用例,打印答案 - 从给定的花环中获得 $$$k$$$ 周期性花环所需的最少移动次数。

示例

输入 #1

6
9 2
010001010
9 3
111100000
7 4
1111111
10 3
1001110101
1 1
1
1 1
0

输出 #1

1
2
5
4
0
0