喵喵题

Problem Description

cats 打算出一场有 $k$ 个题目的比赛，但是 cats 发现他的比赛中所有的题全都是不喵题。cats 对此感到非常郁闷，所以 cats 打算从他的 idea 库里找出一些喵喵题替换掉这场比赛中的题。 cats 的 idea 库可以看作一个长度为 $n$ 的 $01$ 字符串，代表 idea 库中的 $n$ 个题。其中一个 $0$ 代表一个不喵题，一个 $1$ 代表一个喵喵题。在一次操作中，cats 可以选择比赛中任意的 $c$ 个题，将其移除，然后从 idea 库中选择最靠前的 $c$ 个题，将其加入比赛，并从 idea 库中移除。如果 idea 库中剩余的题目数量小于 $c$ 个，则认为 cats 出题失败了。 cats 想在不出题失败的前提下，让自己的比赛中全部的 $k$ 个题都替换为喵喵题。在此基础上，cats 希望最小化他的操作次数。你能帮 cats 求出他最少需要多少次操作吗？如果 cats 无论如何都无法让比赛中全部题都替换为喵喵题，输出 $-1$。

Input

第一行包含一个整数 $T$ （$1\leq T \leq 2\cdot 10^4$），表示一共有 $T$ 组测试数据。 对于每组测试数据： 第一行为两个整数 $n,k$ （$1\leq k\leq n\leq 2\cdot 10^5$），表示 idea 库中题目的总数和比赛中题目的总数。 第二行为一个长度为 $n$ 的 $01$ 字符串，表示 cats 的 idea 库。 保证所有测试数据的 $n$ 之和不超过 $10^6$。

Output

对于每组测试数据，输出一个整数，表示 cats 最少需要的操作次数。如果 cats 无论如何都无法让比赛中全部题都替换为喵喵题，输出 $-1$。

Sample Input

3
6 2
100010
6 2
100011
6 4
100011

Sample Output

4
3
-1

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（6）