Sweets
Contest: Kotlin Heroes: Episode 7
Tags: *special, data structures, implementation

Anya came to her friend's birthday party. There are $$$n$$$ delicious sweets on a circle table (for convenience, we will number them from $$$1$$$ to $$$n$$$ in clockwise direction). For each of the sweets, it is known whether Anya likes it or not. Anya decided that she should eat all the sweets that are on the table, and she likes them.

However, eating all the sweets in some random order is too boring. Therefore, Anya came up with a game that will make the process of eating sweets more interesting.

The game is played according to the following rules:

- if there are no sweets that Anya likes left on the table, then the game ends;
- at the very beginning of the game, if there is at least one sweet on the table that Anya wants to eat, she eats the sweet number $$$1$$$;
- after Anya has eaten some sweet, she counts $$$k$$$ sweets clockwise, starting from the next sweet in the circle, and eats the $$$k$$$-th sweet in the count (if there are less than $$$k$$$ sweets in the circle, some sweets can participate in the count more than once, and the last sweet in the count is picked). Obviously, the sweets that have already been eaten do not participate in the count.

For example, let $$$6$$$ sweets be arranged in a circle, Anya likes sweets $$$4$$$, $$$5$$$ and $$$6$$$, $$$k = 4$$$. Then the game goes as follows:

1. initially there are sweets $$$[1, 2, 3, 4, 5, 6]$$$ on the table, Anya chooses the sweet number $$$1$$$.
2. Anya eats the sweet number $$$1$$$, after that, there are sweets $$$[2, 3, 4, 5, 6]$$$ on the table. Anya counts $$$4$$$ sweets, starting with the $$$2$$$-nd sweet, and stops at the $$$5$$$-th sweet.
3. Anya eats the $$$5$$$-th sweet, after that, there are sweets $$$[2, 3, 4, 6]$$$ on the table. Anya counts $$$4$$$ sweets, starting with the $$$6$$$-th sweet, and stops at the $$$4$$$-th sweet.
4. Anya eats the sweet number $$$4$$$, after that, there are sweets $$$[2, 3, 6]$$$ on the table. Anya counts $$$4$$$ sweets, starting with the $$$6$$$-th sweet, and stops at the $$$6$$$-th sweet.
5. Anya eats the sweet number $$$6$$$, after that, there are sweets $$$[2, 3]$$$ on the table. There are no sweets that Anya likes on the table, so the game ends.

Your task is to calculate the number of sweets that Anya will eat.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 5000$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 5000$$$) — the number of sweets and the parameter $$$k$$$.

The next line contains the string $$$s$$$, where $$$s_i = 1$$$ if Anya likes $$$i$$$-th sweet, and $$$s_i = 0$$$ otherwise.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5000$$$.

Output format:
For each test case, print one integer — the number of sweets that Anya will eat.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
The first test case of the example is described in the statement.

Example input:
4
6 4
000111
7 3
0000100
3 2
000
5 1
10011

Example output:
4
4
0
5

Editorial:
You have to simulate the process described in the statement. Let's consider one of the many approaches to the solution.
Let's store a boolean array $$$used$$$, where sweets will be marked (a sweet $$$i$$$ is marked if $$$used[i]$$$ is true) if Anya has already eaten them. As long as there is at least one index $$$i$$$, such that $$$s_i = 1$$$ and $$$used_i = false$$$, we choose the next sweet that Anya will eat. To find the next sweet, it is enough to run a loop that will find the $$$k$$$-th position from the previous one among the remaining sweets (i. e., those sweets whose values in $$$used$$$ are $$$false$$$).