现在已经是 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^5）。

第二行包含一个字符串 s（|s| = n, s \in { 0，1 } ）表示灯的初始状态。设 s_i 为字符串 s 的第 i 个字符，如果 s_i = 1 ，则第 i 盏灯初始是亮的，否则是灭的。保证 s 中至少有一个 1。

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

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

SNCPC