← 返回题目列表

Codeforces · 1533/C

C. 糖果

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

安雅来参加她朋友的生日聚会。圆桌上有$$$n$$$美味的糖果(为了方便,我们将它们按顺时针方向从$$$1$$$编号到$$$n$$$)。对于每一种糖果,安雅是否喜欢都知道。安雅决定她应该吃掉桌子上所有的糖果,而且她很喜欢它们。

然而,以某种随机的顺序吃所有的糖果太无聊了。因此,安雅想出了一个游戏,让吃甜食的过程变得更加有趣。

游戏按照以下规则进行:

- 如果桌子上没有留下安雅喜欢的糖果,则游戏结束;
- 游戏一开始,如果桌子上至少有一颗糖果安雅想吃,她就吃掉数字$$$1$$$的糖果;
- Anya吃完一些糖果后,从圆圈中的下一个糖果开始顺时针数$$$k$$$个糖果,并吃掉计数中的第$$$k$$$个糖果(如果圆圈中的糖果少于$$$k$$$个,有些糖果可以多次参与计数,并选择计数中的最后一个糖果)。显然,已经吃完的糖果不参与计数。

例如,让 $$$6$$$ 糖果排成一圈,安雅喜欢糖果 $$$4$$$、$$$5$$$ 和 $$$6$$$,$$$k = 4$$$。然后游戏进行如下:

1. 最初桌子上有糖果$$$[1, 2, 3, 4, 5, 6]$$$,安雅选择糖果编号$$$1$$$。
2.安雅吃了数字$$$1$$$的糖果,之后桌子上有糖果$$$[2,3,4,5,6]$$$。 Anya 数 $$$4$$$ 糖果,从第 $$$2$$$ 糖果开始,到第 $$$5$$$ 糖果停止。
3.安雅吃了第$$$5$$$个糖果,之后桌子上有$$$[2,3,4,6]$$$糖果。 Anya 数 $$$4$$$ 糖果,从第 $$$6$$$ 糖果开始,到第 $$$4$$$ 糖果停止。
4.安雅吃了数字$$$4$$$的糖果,之后桌子上有糖果$$$[2,3,6]$$$。 Anya 数 $$$4$$$ 糖果,从第 $$$6$$$ 糖果开始,到第 $$$6$$$ 糖果停止。
5.安雅吃了数字$$$6$$$的糖果,之后桌子上有糖果$$$[2, 3]$$$。桌子上没有安雅喜欢的糖果,所以游戏结束。

你的任务是计算安雅会吃的糖果数量。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 5000$$$) — 测试用例的数量。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le k \le n \le 5000$$$) - 糖果的数量和参数 $$$k$$$。

下一行包含字符串 $$$s$$$,其中如果 Anya 喜欢第 $$$i$$$ 个甜食,则 $$$s_i = 1$$$,否则 $$$s_i = 0$$$。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$5000$$$。

输出

对于每个测试用例,打印一个整数 - Anya 将吃的糖果数量。

示例

输入 #1

4
6 4
000111
7 3
0000100
3 2
000
5 1
10011

输出 #1

4
4
0
5

注意

示例的第一个测试用例在语句中进行了描述。