现在已经是 21:30 了，是时候让 BaoBao 上床睡觉了。为了保证睡眠质量，BaoBao 决定关掉卧室里所有的灯。

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

给定所有灯的初始状态，请帮助 BaoBao 确定最小的 $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$。

样例

输入 1

2
10 4
0101011111
3 1
010

输出 1

3
1