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

卧室里有 $n$ 盏灯，从 $1$ 到 $n$ 编号，排成一排。每次宝宝可以选择一个整数 $i$，并关闭从 $i$ 到 $(i+L−1)$ 编号的所有灯（包括这两盏），其中 $L$ 是一个预先定义的正整数。请注意，每次选择的 $L$ 必须相同。

给定所有灯的初始状态，请帮助宝宝确定最小可能的 $L$，以便他可以在 $K$ 次内关闭所有灯。

输入格式

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

第一行包含两个整数 $n$ 和 $k（1≤k≤n≤2×10^5）$。

第二行包含一个字符串 $s（∣s∣=n，s∈{0,1}）$，表示灯的初始状态。如果 $s_i=1$，则表示第 $i$ 盏灯最初是开着的，否则它最初是关着的。保证 $s$ 中至少有一个 1。

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

输出格式

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

样例 #1

样例输入 #1

2
10 4
0101011111
3 1
010

样例输出 #1

3
1