Little Cyan Fish possède une rangée de $n$ boules. Chaque boule est soit cyan, soit blanche. La rangée est décrite par une chaîne $s$ de longueur $n$, où C désigne une boule cyan et W désigne une boule blanche.

Lors d'une opération, il choisit une boule cyan dans la rangée actuelle. Supposons que cette boule soit à la position $i$ dans la rangée actuelle. Alors, toutes les boules dont la position diffère de $i$ d'au plus $k$ sont supprimées, y compris la boule cyan choisie elle-même. Après la suppression, les parties restantes à gauche et à droite sont concaténées.

Par exemple, lorsque $k = 1$, une opération possible est

où la boule avec la bordure épaisse est choisie et les boules à l'intérieur de la boîte rouge sont supprimées.

Trouvez le nombre minimum d'opérations nécessaires pour supprimer toute la rangée. Si c'est impossible, indiquez-le.

Entrée

Il y a plusieurs cas de test. La première ligne de l'entrée contient un entier unique $T$ ($1 \le T$), indiquant le nombre de cas de test.

Pour chaque cas de test, la première ligne contient deux entiers $n$ et $k$ ($1 \le k \le n \le 10^6$). La deuxième ligne contient une chaîne $s$ de longueur $n$, composée uniquement des caractères C et W.

Il est garanti que la somme de $n$ sur tous les cas de test ne dépasse pas $10^6$.

Sortie

Pour chaque cas de test, s'il est impossible de supprimer toute la rangée, affichez une seule ligne avec un entier unique $-1$. Sinon, affichez une seule ligne contenant un entier unique, indiquant le nombre minimum d'opérations nécessaires pour supprimer toute la rangée.

Exemples

Entrée 1

3
1 1
C
5 2
WWCWW
4 1
WWWW

Sortie 1

1
1
-1

Remarque

Dans le premier cas de test, Little Cyan Fish choisit la seule boule présente.

Dans le deuxième cas de test, il choisit la boule cyan du milieu ; comme $k = 2$, toute la rangée est supprimée en une seule opération.

Dans le troisième cas de test, il n'y a pas de boule cyan, donc aucune opération ne peut être effectuée.