CF2259A.Moo Language School

Farmer John is trying to increase literacy rates in the United Cows of Farmer John (UCFJ). The UCFJ consists of $n$ fields and $\frac{n}{k}$ farms (where $n$ is a multiple of $k$), with each farm consisting of $k$ consecutive fields. In other words, the $i$-th field is in the $\lceil \frac{i}{k} \rceil$-th farm: Fields $1, 2, \ldots, k$ are in the first farm, fields $k+1, k+2, \ldots, 2k$ are in the second farm, etc.

Farmer John wants to build schools such that each farm has at least one school. However, some fields are owned by Farmer Nhoj, who will charge Farmer John extra to build a school there. Farmer John wants to know the minimum number of times that he would have to build a school on Farmer Nhoj's land in order to ensure that each farm has at least one school.

农夫约翰正试图提高“农夫约翰联合奶牛”（UCFJ）的识字率。UCFJ 由 $n$ 块田地和 $\frac{n}{k}$ 个农场组成（其中 $n$ 是 $k$ 的倍数），每个农场恰好包含 $k$ 块连续的田地。换言之，第 $i$ 块田地属于第 $\lceil \frac{i}{k} \rceil$ 个农场：第 $1, 2, \ldots, k$ 块田地属于第一个农场，第 $k+1, k+2, \ldots, 2k$ 块田地属于第二个农场，依此类推。

农夫约翰希望修建若干所学校，使得每个农场至少拥有一所学校。然而，部分田地归农夫诺杰（Farmer Nhoj）所有；若在这些田地上建校，农夫诺杰将向农夫约翰额外收费。农夫约翰想知道：为确保每个农场至少拥有一所学校，他最少需要在农夫诺杰的田地上建多少所学校？

The first line of each input contains an integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases.

The first line of each test case contains two integers $n$ and $k$ ($1 \leq k \leq n \leq 20$, $n$ is a multiple of $k$) — the number of fields and size of each farm.

The second line of each test case contains a binary string $s$ of length $n$ — the fields owned by Farmer Nhoj. If $s_i = 1$, the $i$-th field is owned by Farmer Nhoj. If $s_i = 0$, the $i$-th field is not owned by Farmer Nhoj.

每组输入的第一行包含一个整数 $t$（$1 \leq t \leq 10^4$）—— 表示测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \leq k \leq n \leq 20$，且 $n$ 是 $k$ 的倍数）—— 分别表示田地总数以及每座农场的大小。

每个测试用例的第二行包含一个长度为 $n$ 的二进制字符串 $s$ —— 表示 Farmer Nhoj 拥有的田地。若 $s_i = 1$，则第 $i$ 块田地归 Farmer Nhoj 所有；若 $s_i = 0$，则第 $i$ 块田地不属于 Farmer Nhoj。

For each test case, output a single integer — the minimum number of times that Farmer John must build a school on Farmer Nhoj's land.

对于每个测试用例，输出一个整数——农夫约翰必须在农夫诺杰的土地上建造学校的最少次数。

For the first test case, we can build a school on the $2$nd, $3$rd, $5$th, and $7$th fields, and of those, only the $5$th field is owned by Farmer Nhoj, meaning our answer is $1$. It can be shown that this is the best possible answer.

For the second test case, Farmer Nhoj owns every field, and since we have to build $5$ schools, we must build on Farmer Nhoj's land $5$ times.

对于第一个测试用例，我们可以在第 $2$、第 $3$、第 $5$ 和第 $7$ 块田地上建造学校，其中仅有第 $5$ 块田地属于 Farmer Nhoj，因此答案为 $1$。可以证明这是最优解。

对于第二个测试用例，Farmer Nhoj 拥有全部田地，而我们必须建造 $5$ 所学校，因此必须在 Farmer Nhoj 的土地上建造 $5$ 次。