Kotlin Heroes: Episode 7 |
---|
Finished |
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:
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:
Your task is to calculate the number of sweets that Anya will eat.
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$$$.
For each test case, print one integer — the number of sweets that Anya will eat.
4 6 4 000111 7 3 0000100 3 2 000 5 1 10011
4 4 0 5
The first test case of the example is described in the statement.
Name |
---|