题目内容

在一个环形赛道上，共有 $n$ 个位置按顺时针排列，每个位置要么是补给点（用 1 表示），要么是普通路段（用 0 表示）。这些标记按顺时针顺序构成长度为 $n$ 的字符串 $s$。

你可以自由选择一个位置作为起点，从该位置出发沿顺时针方向行驶，按经过的顺序读取标记，形成一个线性序列。在该序列中，我们关心最短的包含恰好 $k$ 个 1 的前缀（即恰好经过 $k$ 个补给点），称这个前缀的长度为从该起点出发的代价。你需要求出所有可能起点下代价的最小值。

若整个赛道中补给点的总数不足 $k$，则无论从何处出发都无法达成目标，此时答案为 -1。

【约束】

所有测试数据的 $n$ 之和不超过 $2 \times 10^5$，每组数据中 $1 \le k \le n$。

输入描述

第一行包含一个整数 $T$，表示测试数据的组数（$1 \le T \le 10^5$）。 接下来每组数据包含两行：第一行包含两个整数 $n$ 和 $k$，第二行包含一个长度为 $n$ 的字符串 $s$，$s$ 仅由字符 1 和 0 组成。

输出描述

对于每组测试数据，输出一行一个整数，表示满足条件的最小代价；若无法达成目标，则输出 -1。

样例1

输入

3
6 2
101010
5 2
00001
4 4
1111

输出

3
-1
4

说明

第一组数据：$n=6,k=2,s=\text{101010}$。字符串中 1 的位置依次为 $0,2,4$。枚举每个 1 作为起点，找顺时针第 $k$ 个 1：起点为位置 0 时，前两个 1 的下标为 0 和 2，区间长度为 $2-0+1=3$；起点为 2 时，区间 $2$ 到 $4$ 长度为 3；起点为 4 时，需跨过环末尾到 0（等价于 6），区间 $4$ 到 $6$ 长度也为 3。最小代价为 3。

第二组数据：$n=5,k=2,s=\text{00001}$。整个赛道只有一个补给点（1），总数 $1 < k=2$，无法从任何起点读到恰好 $2$ 个 1，因此输出 -1。

第三组数据：$n=4,k=4,s=\text{1111}$。所有位置都是补给点，要包含恰好 $4$ 个 1，必须走完整个环，区间长度恒为 4，最小代价为 4。

样例2

输入

1
5 1
00000

输出

-1

说明

$n=5,k=1,s=\text{00000}$。字符串中没有 1，补给点总数 $0 < k=1$，无法找到包含至少一个补给点的情况，答案为 -1。

样例3

输入

1
10 3
1001001001

输出

5

说明

$n=10,k=3,s=\text{1001001001}$。1 的位置依次为 $0,3,6,9$。

若以位置 0 为起点，第三个 1 在位置 6，路径长度 $6-0+1=7$； 以位置 3 为起点，第三个 1 在位置 9，长度 $9-3+1=7$； 以位置 6 为起点，第三个 1 需要跨过环末尾，等价于位置 $0+10=10$，区间 $6$ 到 $10$ 长度 $10-6+1=5$； 以位置 9 为起点，第三个 1 等价于位置 $3+10=13$，区间 $9$ 到 $13$ 长度 $13-9+1=5$。

所有方案中最小长度为 5，因此代价最小值为 5。