You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 3.0 seconds
Memory limit: 256.0 MB

# Problem
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.

## Examples
```input
4
6 4
000111
7 3
0000100
3 2
000
5 1
10011
```
```output
4
4
0
5
```

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

Now solve the problem and return the code.