Little Cyan Fish は $n$ 個のボールを一列に並べて持っている。各ボールはシアン色か白色のいずれかである。この列は長さ $n$ の文字列 $s$ で表され、C はシアン色のボール、W は白色のボールを意味する。

1 回の操作で、彼は現在の列にあるシアン色のボールを 1 つ選ぶ。このボールが現在の列の $i$ 番目の位置にあるとする。すると、位置 $i$ との差が $k$ 以内であるすべてのボールが、選んだシアン色のボール自身を含めて削除される。削除後、残った左側の部分と右側の部分が連結される。

例えば、$k = 1$ のとき、考えられる操作の 1 つは以下の通りである。

太い枠で囲まれたボールが選ばれ、赤枠内のボールが削除される。

列全体を削除するために必要な最小の操作回数を求めよ。不可能である場合は、その旨を報告せよ。

入力

入力は複数のテストケースからなる。最初の行にはテストケースの数を示す整数 $T$ ($1 \le T$) が含まれる。

各テストケースの最初の行には、2 つの整数 $n$ と $k$ ($1 \le k \le n \le 10^6$) が含まれる。2 行目には、C と W のみからなる長さ $n$ の文字列 $s$ が含まれる。

すべてのテストケースにおける $n$ の総和は $10^6$ を超えないことが保証される。

出力

各テストケースについて、列全体を削除することが不可能な場合は、$-1$ を 1 行に出力せよ。可能な場合は、列全体を削除するために必要な最小の操作回数を 1 行に出力せよ。

入出力例

入力 1

3
1 1
C
5 2
WWCWW
4 1
WWWW

出力 1

1
1
-1

注記

最初のサンプルテストケースでは、Little Cyan Fish は唯一のボールを選ぶ。

2 番目のサンプルテストケースでは、彼は中央のシアン色のボールを選ぶ。$k = 2$ であるため、1 回の操作で列全体が削除される。

3 番目のサンプルテストケースでは、シアン色のボールが存在しないため、操作を行うことはできない。