Alice 和 Bob 参加钓鱼比赛!他们总共捕获了$$$n$$$条鱼,编号从$$$1$$$到$$$n$$$(鱼越大,其指数越大)。其中一些鱼是爱丽丝捕获的,其他鱼是鲍勃捕获的。
他们的表现将评估如下。首先,将选择一个整数$$$m$$$,所有鱼将被分成$$$m$$$非空组。第一组应包含几条(至少一条)最小的鱼,第二组应包含几条(至少一条)次小的鱼,依此类推。每条鱼都应该属于一个组,并且每个组都应该是鱼的连续子段。请注意,这些组完全按照该顺序编号;例如,第二组中的鱼不能小于第一组中的鱼,因为第一组中包含最小的鱼。
然后,每条鱼将根据其组索引分配一个值:第一组中的每条鱼的值等于 $$$0$$$,第二组中的每条鱼的值等于 $$$1$$$,依此类推。因此,第 $$$i$$$ 组中的每条鱼的价值等于 $$$(i-1)$$$。
每位参赛者的得分就是参赛者捕获的所有鱼的总价值。
您希望 Bob 的分数超过 Alice 的分数至少 $$$k$$$ 分。您必须将鱼分成多少组($$$m$$$)?如果不可能,您应该报告这一情况。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$1 \le k \le 10^9$$$)。
第二行包含一个字符串,由 $$$n$$$ 个字符组成。第 $$$i$$$ 字符要么是 0(表示第 $$$i$$$ 条鱼被 Alice 捕获),要么是 1(表示第 $$$i$$$ 条鱼被 Bob 捕获)。
对输入的附加约束:所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数 - 您必须将鱼分成的最小组数;如果不可能,则为 -1。
示例
输入 #1
7 4 1 1001 4 1 1010 4 1 0110 4 2 0110 6 3 001110 10 20 1111111111 5 11 11111
输出 #1
2 -1 2 -1 3 4 -1
注意
在示例的第一个测试用例中,您可以按如下方式将鱼分成组:前三条鱼形成 $$$1$$$-st 组,最后一条鱼形成 $$$2$$$-nd 组。那么,Bob 的分数将为 $$$1$$$,Alice 的分数将为 $$$0$$$。
在示例的第三个测试用例中,您可以按如下方式将鱼分成组:第一条鱼形成 $$$1$$$-st 组,最后三条鱼形成 $$$2$$$-nd 组。那么,Bob 的分数将为 $$$2$$$,Alice 的分数将为 $$$1$$$。