安雅来参加她朋友的生日聚会。圆桌上有$$$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
注意
示例的第一个测试用例在语句中进行了描述。