#P18381. White Night 2
White Night 2
White Night 2
题目描述
小青鱼有一排共 个球。每个球为青色或白色。这一排球由长度为 的字符串 描述,其中 C 表示青色球,W 表示白色球。
一次操作中,他选择当前球列中的一个青色球。假设这个球当前位于第 个位置,那么删除所有与位置 的差的绝对值不超过 的球,包括选中的青色球自身。删除后,将剩余的左半部分和右半部分直接拼接起来。
例如,当 时,可以执行如下操作。粗边框标出的球是选中的青色球,红框内的球会被删除。

请你求出删除整排球所需的最少操作次数。如果无法删除全部球,请报告无解。
输入格式
输入包含多组测试数据。第一行包含整数 (),表示测试数据组数。
对于每组测试数据:
第一行包含两个整数 ()。
第二行包含长度为 的字符串 ,其中仅包含字符 C 和 W。
保证所有测试数据的 之和不超过 。
输出格式
对于每组测试数据,如果无法删除整排球,输出一行一个整数 ;否则输出一行一个整数,表示最少操作次数。
样例输入
3
1 1
C
5 2
WWCWW
4 1
WWWW
样例输出
1
1
-1
样例说明
第一组数据,小青鱼选择唯一的球即可。
第二组数据,选择中间的青色球。由于 ,一次操作就会删除整排球。
第三组数据,没有青色球,无法执行任何操作。