Little Cyan Fish 有一排 $n$ 個球。每個球不是青色就是白色。這排球由一個長度為 $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$，整排球在一次操作中被刪除。

在第三個範例測試資料中，沒有青色球，因此無法進行任何操作。