题目描述

现在已经是 21:30 了，宝宝该上床睡觉了。为了确保他的睡眠质量，宝宝决定关掉卧室里的所有灯。

宝宝的卧室里有 $n$ 盏灯，从1到 $n$ 排成一排。每次宝宝可以选择一个整数 $i$，并将从第 $i$ 盏灯到第 $(i+L-1)$ 盏灯（包括两端）之间的所有灯关掉，其中 $L$ 是一个预定义的正整数。注意，每次操作的 $L$ 值必须相同。

给定所有灯的初始状态，请帮助宝宝确定可能的最小 $L$ 使得他能在 $k$ 次操作内关掉所有的灯。

输入格式

有多个测试用例。输入的第一行包含一个整数 $T$，表示测试用例的数量。对于每个测试用例：

第一行包含两个整数 $n$ 和 $k$（$1 \le k \le n \le 2 \times 10^6$）。

第二行包含一个字符串 $s$（$s$ 的长度为 $n$，设 $s_i$ 为字符串 $s$ 的第 $i$ 个字符，如果 $s_i = 1$，则第 $i$ 盏灯初始是亮的，否则是灭的。保证 $s$ 中至少有一个 $1$。）

保证所有测试用例的 $n$ 之和不超过 $2 \times 10^6$。

输出格式

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

样例输入

2
10 4
0101011111
3 1
010

样例输出

3
1