CF2259A Moo Language School

Farmer John 正在努力提高 Farmer John 联合奶牛国（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 John 想要建设学校，使每个农场至少有一所学校。然而，部分田地归 Farmer Nhoj 所有，在这些田地建校会让 Farmer John 付出额外的费用。Farmer John 想知道，为了保证每个农场至少有一所学校，他最少不得不在 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$，则不归他所有。

对于每个测试用例，输出一个整数，表示 Farmer John 至少需要在 Farmer Nhoj 的田地上建校的最小次数。

对于第一个测试用例，我们可以选择在第 $2$、$3$、$5$ 和 $7$ 块田地上建校，其中只有第 $5$ 块田地归 Farmer Nhoj 所有，所以答案为 $1$。可以证明这是最优答案。 对于第二个测试用例，所有田地都归 Farmer Nhoj 所有，由于必须建 $5$ 所学校，所以必须在 Farmer Nhoj 的田地上建 $5$ 次学校。 由 ChatGPT 5 翻译