T434251 「YAC Round 7」晚安，爱丽丝


爱丽丝该睡觉了。为了保证她的睡眠质量，爱丽丝的男朋友魔理沙（所以魔理沙真的是男孩子吗？）决定关掉她卧室里的所有灯。 爱丽丝的卧室里有 $n$ 盏灯，编号从 1 到 $n$ 排列成一排。每次魔理沙都可以选择一个整数 $i$，然后关闭所有编号从 $i$ 到 $(i+L-1)$（包括这两个整数）的灯，其中 $L$ 是一个预定义的正整数。每次关灯操作 $L$ 的值必须相同。 给定一个字符串，表示所有灯的初始状态，其中 $\text{'0'}$ 表示灯灭，$\text{'1'}$ 表示灯亮。 请帮助魔理沙确定一个 **最小的 $L$**，并且能在 $k$ 次操作内关闭所有灯。

**有多个测试用例。** 输入的第一行包含一个整数 $T$，表示测试用例的数量。 对于每个测试用例: 第一行包含两个整数 $n$ 和 $k$（$1 \le k \le n \le 2 \times 10^5$）。 第二行包含一个字符串 $s$ $\;$ ($|s| = n$, $s \in \{ \text{'0'},\text{'1'} \}$)，表示灯的初始状态。 假设 $s_i$ 是 $s$ 中的第 $i$ 个字符，如果 $s_i = \text{'1'}$，则第 $i$ 个灯初始为亮，否则初始为灭。保证 $s$ 中至少有一个 $\text{'1'}$。 保证所有测试样例的 $n$ 之和不超过 $2 \times 10^6$。

对每个测试用例输出一行，其中包含一个整数，表示最小的 $L$。