题目描述

已经晚上九点半了，小宝决定关掉卧室里所有的灯，然后上床睡觉。

卧室里有 $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 \{\text{<code>0'}, \text{</code>1'}\}$），表示所有灯的初始状态。设 $s_i$ 为 $s$ 的第 $i$ 个字符，若 $s_i = \text{<code>1'}$ 则第 $i$ 盏灯初始为亮，否则为灭。保证 $s$ 中至少有一个 </code>1`。

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

输出格式

对于每组测试数据输出一行，包含一个整数，表示最小的 $L$。

样例

2
10 4
0101011111
3 1
010

3
1