Little Cyan Fish 有一排 $n$ 个球。每个球要么是青色（cyan）的，要么是白色（white）的。这一排球由一个长度为 $n$ 的字符串 $s$ 描述，其中 C 表示青色球，W 表示白色球。

在一次操作中，他会在当前这一排球中选择一个青色球。假设该球在当前排中的位置为 $i$。那么，所有与位置 $i$ 的距离不超过 $k$ 的球都会被删除，包括被选中的那个青色球本身。删除后，剩余的左侧部分和右侧部分会拼接在一起。

例如，当 $k = 1$ 时，一种可能的操作是：

其中带有粗边框的球被选中，红框内的球被删除。

求删除整排球所需的最少操作次数。如果无法删除，请报告。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$ ($1 \le T$)，表示测试数据的组数。

对于每组测试数据，第一行包含两个整数 $n$ 和 $k$ ($1 \le k \le n \le 10^6$)。第二行包含一个长度为 $n$ 的字符串 $s$，仅由字符 C 和 W 组成。

保证所有测试数据的 $n$ 之和不超过 $10^6$。

输出格式

对于每组测试数据，如果无法删除整排球，输出一行，包含一个整数 $-1$。否则，输出一行，包含一个整数，表示删除整排球所需的最少操作次数。

样例

样例输入 1

3
1 1
C
5 2
WWCWW
4 1
WWWW

样例输出 1

1
1
-1

说明

在第一个样例测试中，Little Cyan Fish 选择了唯一的那个球。

在第二个样例测试中，他选择了中间的青色球；因为 $k = 2$，整排球在一次操作中被删除。

在第三个样例测试中，没有青色球，因此无法进行任何操作。