Little Cyan Fish ma rząd $n$ kul. Każda kula jest albo cyjanowa, albo biała. Rząd opisany jest ciągiem $s$ o długości $n$, gdzie C oznacza kulę cyjanową, a W oznacza kulę białą.

W jednej operacji wybiera on kulę cyjanową w bieżącym rzędzie. Załóżmy, że ta kula znajduje się na pozycji $i$ w bieżącym rzędzie. Wtedy wszystkie kule, których pozycje różnią się od $i$ o co najwyżej $k$, zostają usunięte, wliczając w to samą wybraną kulę cyjanową. Po usunięciu, pozostałe lewe i prawe części są ze sobą łączone.

Na przykład, gdy $k = 1$, jedną z możliwych operacji jest

gdzie wybrana jest kula z grubą obwódką, a kule wewnątrz czerwonej ramki zostają usunięte.

Znajdź minimalną liczbę operacji potrzebną do usunięcia całego rzędu. Jeśli jest to niemożliwe, zgłoś to.

Wejście

Dostępnych jest wiele przypadków testowych. Pierwsza linia wejścia zawiera pojedynczą liczbę całkowitą $T$ ($1 \le T$), oznaczającą liczbę przypadków testowych.

Dla każdego przypadku testowego, pierwsza linia zawiera dwie liczby całkowite $n$ oraz $k$ ($1 \le k \le n \le 10^6$). Druga linia zawiera ciąg $s$ o długości $n$, składający się wyłącznie ze znaków C oraz W.

Gwarantuje się, że suma $n$ we wszystkich przypadkach testowych nie przekracza $10^6$.

Wyjście

Dla każdego przypadku testowego, jeśli usunięcie całego rzędu jest niemożliwe, wypisz w pojedynczej linii liczbę $-1$. W przeciwnym razie wypisz w pojedynczej linii pojedynczą liczbę całkowitą, oznaczającą minimalną liczbę operacji potrzebną do usunięcia całego rzędu.

Przykład

Wejście 1

3
1 1
C
5 2
WWCWW
4 1
WWWW

Wyjście 1

1
1
-1

Uwagi

W pierwszym przypadku testowym Little Cyan Fish wybiera jedyną dostępną kulę.

W drugim przypadku testowym wybiera środkową kulę cyjanową; ponieważ $k = 2$, cały rząd zostaje usunięty w jednej operacji.

W trzecim przypadku testowym nie ma żadnej kuli cyjanowej, więc nie można wykonać żadnej operacji.