你有一条长度为 $$$n$$$ 的方格纸条。每个单元格要么是白色的,要么是黑色的。
为了在条纹上有 $$$k$$$ 连续黑色单元段,必须从白色重新着色为黑色的单元格的最小数量是多少?
如果输入数据已经存在一段 $$$k$$$ 连续黑色单元格,则打印 0。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
接下来是 $$$t$$$ 测试用例的描述。
输入的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le k \le n \le 2\cdot10^5$$$)。第二行由字母“W”(白色)和“B”(黑色)组成。线路长度为$$$n$$$。
保证 $$$n$$$ 值的总和不超过 $$$2\cdot10^5$$$。
输出
对于每个 $$$t$$$ 测试用例,打印一个整数 - 需要从白色重新绘制为黑色才能获得一段 $$$k$$$ 连续黑色单元的最小单元数。
示例
输入 #1
4 5 3 BBWBW 5 5 BBWBW 5 1 BBWBW 1 1 W
输出 #1
1 2 0 1
注意
在第一个测试用例中,$$$s$$$="BBWBW" 和 $$$k=3$$$。重新着色 $$$s_3$$$ 并得到 $$$s$$$="BBBBW" 就足够了。该字符串包含长度为 $$$k=3$$$ 的段,由字母“B”组成。
在示例 $$$s$$$="BBWBW" 和 $$$k=5$$$ 的第二个测试用例中。重新着色 $$$s_3$$$ 和 $$$s_5$$$ 并得到 $$$s$$$="BBBBB" 就足够了。该字符串包含长度为 $$$k=5$$$ 的段,由字母“B”组成。
在示例 $$$s$$$="BBWBW" 和 $$$k=1$$$ 的第三个测试用例中。字符串 $$$s$$$ 已包含长度为 $$$k=1$$$ 且由字母“B”组成的段。