Background

农夫john养了两种奶牛, 他们喜欢吃不同的草

Description

现在有$n$块草坪排成一排, 上面站着$n$头奶牛, 完美用$G$表示$G$奶牛, 喜欢吃$G$草; 用$H$表示$H$奶牛, 喜欢吃$H$草.

现在奶牛们有一个最大的移动距离$k$, 表示每只奶牛最多可以走$k$块草坪去吃喜欢的草.

每块草坪都足够大, 不会出现吃光光的情况.

现在希望你规划一下, 最少种植多少草坪即可?

Format

Input

第一行一个整数$t$, 表示有多组数据

接下来每组数据的第一行两个整数$n, k$, 表示草坪数量和奶牛最远移动的距离.

接下来$n$头奶牛的代号, 用$G, H$表示

Output

对于每组数据, 输出一个整数, 表示最少种植的草坪数量

Samples

5
5 0
GHHGG
5 1
GHHGG
5 2
GHHGG
5 3
GHHGG
5 4
GHHGG

5
3
2
2
2

样例解释

方案可能不唯一, 请找到最小的种植草坪数

5 0 GHHGG 5 GHHGG

5 1 GHHGG 3 .GH.G

5 2 GHHGG 2 ..GH.

5 3 GHHGG 2 ...GH

5 4 GHHGG 2 ...HG

Limitation

$1 <= t <= 50$

$0 <= k<=n <= 10^5$