CF1367C.Social Distance

Polycarp and his friends want to visit a new restaurant. The restaurant has $n$ tables arranged along a straight line. People are already sitting at some tables. The tables are numbered from $1$ to $n$ in the order from left to right. The state of the restaurant is described by a string of length $n$ which contains characters "1" (the table is occupied) and "0" (the table is empty).

Restaurant rules prohibit people to sit at a distance of $k$ or less from each other. That is, if a person sits at the table number $i$, then all tables with numbers from $i-k$ to $i+k$ (except for the $i$-th) should be free. In other words, the absolute difference of the numbers of any two occupied tables must be strictly greater than $k$.

For example, if $n=8$ and $k=2$, then:

• strings "10010001", "10000010", "00000000", "00100000" satisfy the rules of the restaurant;
• strings "10100100", "10011001", "11111111" do not satisfy to the rules of the restaurant, since each of them has a pair of "1" with a distance less than or equal to $k=2$.

In particular, if the state of the restaurant is described by a string without "1" or a string with one "1", then the requirement of the restaurant is satisfied.

You are given a binary string $s$ that describes the current state of the restaurant. It is guaranteed that the rules of the restaurant are satisfied for the string $s$.

Find the maximum number of free tables that you can occupy so as not to violate the rules of the restaurant. Formally, what is the maximum number of "0" that can be replaced by "1" such that the requirement will still be satisfied?

For example, if $n=6$, $k=1$, $s=$ "100010", then the answer to the problem will be $1$, since only the table at position $3$ can be occupied such that the rules are still satisfied.

波利卡普和他的朋友们想去一家新餐厅。这家餐厅有 $n$ 张桌子沿一条直线排列。部分桌子已被占用。桌子从左到右依次编号为 $1$ 到 $n$。餐厅当前状态由一个长度为 $n$ 的字符串描述，其中字符 "1" 表示该桌子已被占用，字符 "0" 表示该桌子为空。

餐厅规定：任何人不得坐在彼此距离不超过 $k$ 的位置上。即，若某人坐在编号为 $i$ 的桌子，则所有编号在区间 $[i-k,\, i+k]$ 内（除第 $i$ 张桌子外）的桌子都必须为空。换言之，任意两张被占用桌子的编号之差的绝对值必须严格大于 $k$。

例如，当 $n=8$ 且 $k=2$ 时：

• 字符串 "10010001"、"10000010"、"00000000"、"00100000" 满足餐厅规则；
• 字符串 "10100100"、"10011001"、"11111111" 不满足餐厅规则，因为其中每条字符串均存在一对 "1"，其位置距离小于或等于 $k=2$。

特别地，若字符串中不含 "1"，或仅含一个 "1"，则餐厅规则自动满足。

现给定一个二进制字符串 $s$，用于描述餐厅当前状态。题目保证字符串 $s$ 满足餐厅规则。

求：在不违反餐厅规则的前提下，最多还能占用多少张空桌？形式化地说，即最多可将多少个 "0" 替换为 "1"，使得规则仍被满足？

例如，当 $n=6$、$k=1$、$s=$ "100010" 时，问题的答案为 $1$，因为只有位置 $3$ 上的桌子可以被占用，同时仍满足规则。

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases in the test. Then $t$ test cases follow.

Each test case starts with a line containing two integers $n$ and $k$ ($1 \le k \le n \le 2\cdot 10^5$) — the number of tables in the restaurant and the minimum allowed distance between two people.

The second line of each test case contains a binary string $s$ of length $n$ consisting of "0" and "1" — a description of the free and occupied tables in the restaurant. The given string satisfy to the rules of the restaurant — the difference between indices of any two "1" is more than $k$.

The sum of $n$ for all test cases in one test does not exceed $2\cdot 10^5$.

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 测试用例的数量。随后是 $t$ 个测试用例。

每个测试用例以一行开始，该行包含两个整数 $n$ 和 $k$（$1 \le k \le n \le 2\cdot 10^5$）—— 分别表示餐厅中桌子的总数以及两人之间允许的最小距离。

每个测试用例的第二行包含一个长度为 $n$ 的二进制字符串 $s$，由字符 "0" 和 "1" 组成 —— 描述餐厅中空闲与已被占用的桌子。给定字符串满足餐厅规则：任意两个 "1" 的下标之差严格大于 $k$。

所有测试用例的 $n$ 值之和不超过 $2\cdot 10^5$。

For each test case output one integer — the number of tables that you can occupy so as not to violate the rules of the restaurant. If additional tables cannot be taken, then, obviously, you need to output $0$.

对于每个测试用例，输出一个整数——在不违反餐厅规则的前提下，你可以占据的桌子数量。如果无法再占用额外的桌子，则显然需要输出 $0$。

The first test case is explained in the statement.

In the second test case, the answer is $2$, since you can choose the first and the sixth table.

In the third test case, you cannot take any free table without violating the rules of the restaurant.

第一个测试用例已在题目描述中说明。

在第二个测试用例中，答案为 $2$，因为你可以选择第一张和第六张桌子。

在第三个测试用例中，你无法在不违反餐厅规则的前提下选取任何空闲桌子。