#P18381. White Night 2

White Night 2

White Night 2

题目描述

小青鱼有一排共 nn 个球。每个球为青色或白色。这一排球由长度为 nn 的字符串 ss 描述,其中 C 表示青色球,W 表示白色球。

一次操作中,他选择当前球列中的一个青色球。假设这个球当前位于第 ii 个位置,那么删除所有与位置 ii 的差的绝对值不超过 kk 的球,包括选中的青色球自身。删除后,将剩余的左半部分和右半部分直接拼接起来。

例如,当 k=1k=1 时,可以执行如下操作。粗边框标出的球是选中的青色球,红框内的球会被删除。

选球与删除范围示意

请你求出删除整排球所需的最少操作次数。如果无法删除全部球,请报告无解。

输入格式

输入包含多组测试数据。第一行包含整数 TT(T≥1T\ge1),表示测试数据组数。

对于每组测试数据:

第一行包含两个整数 n,kn,k(1≤k≤n≤1061\le k\le n\le10^6)。

第二行包含长度为 nn 的字符串 ss,其中仅包含字符 C 和 W。

保证所有测试数据的 nn 之和不超过 10610^6。

输出格式

对于每组测试数据,如果无法删除整排球,输出一行一个整数 −1-1;否则输出一行一个整数,表示最少操作次数。

样例输入

3
1 1
C
5 2
WWCWW
4 1
WWWW

样例输出

1
1
-1

样例说明

第一组数据,小青鱼选择唯一的球即可。

第二组数据,选择中间的青色球。由于 k=2k=2,一次操作就会删除整排球。

第三组数据,没有青色球,无法执行任何操作。