题目描述

警报！火灾正在吞噬森林！

这片森林的形状像一个环，可以分为 $n$ 个部分。第 $i$ 部分（$1 \leq i \leq n$）仅与第 $( i - 2 \mod n )+1$ 部分和第 $( i \mod n )+1$ 部分相邻。如果不采取任何行动，并且某一时刻第 $i$ 部分发生火灾，则其相邻部分将在这一时刻后的一分钟内被火焰吞噬。

作为一个负责任的居民，你已经拨打了消防员的电话，希望他们尽快赶来扑灭这场可怕的火灾。然而，他们到达这里需要 $t_0$ 分钟。你能做些什么吗？

可以的！你决定在森林的一个部分上点燃可控的火，以便在火灾到达这个区域之前立即建立一个火灾隔离区，也就是建立一个隔离带。这样，火灾就无法在此地蔓延。

但是，做出明智的决定是困难的：你需要选择火灾隔离区的位置，以确保更多的森林部分不被烧毁。在消防员到达之前，你能得到的最大的不被烧毁部分数量是多少？

输入格式

每组测试包含多个测试用例。第一行包含测试用例的数量 $T$（$1 \leq T \leq 10^4$）。

每个测试用例由 $2$ 行组成。

第一行包含两个整数 $n, t_0$（$1 \leq n, t_0 \leq 10^5$），表示森林中的部分数量和消防员到达森林所需的分钟数。

第二行包含一个字符串 $s$（$|s| = n$），该字符串由 0 和 1 组成。第 $i$ 部分正在着火，当且仅当 $s_i = 1$。保证存在一个 $i$（$1 \leq i \leq n$）使得 $s_i = 1$。

保证在单组测试中，$\sum n$ 不会超过 $5 \times 10^5$。

输出格式

对于每个测试用例，输出一个整数 — 当消防员到达时，森林中未烧毁部分的最小数量。

3
5 2
10000
5 3
10000
10 1
1000000100

1
0
4

解释 #1

对于第一个测试用例，一旦你点燃第 $2$ 部分，火灾只会有时间烧毁第 $4$ 和 $5$ 部分，留下第 $3$ 部分未烧毁。