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

宝宝的卧室里有n盏灯，编号从1到n，排列成一排。每次宝宝都可以选择一个整数i，并关闭从i到i+L−1（包括两者）的所有灯，其中L是自定义的正整数。
请注意，每次L的值都必须相同。
考虑到所有灯的初始状态，请帮助宝宝确定尽可能小的L，以便他可以在k次内关闭所有灯。

输入格式
有多个测试用例。
输入的第一行包含一个整数T，表示测试用例的数量。对于每个测试用例：
第一行包含两个整数n和k(1≤k≤n≤2×$10^{5}$)
第二行包含字符串s(字符串长度为n，只含0和1）去代表灯的初始状态。其中，字符串中第i个字符代表第i盏灯的状态。1代表灯亮，0代表灯灭，保证至少有一盏灯是亮的状态。
保证所有测试用例的n之和不会超过2×$10^{6}$

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