Little Cyan Fish tiene una fila de $n$ bolas. Cada bola es cian o blanca. La fila se describe mediante una cadena $s$ de longitud $n$, donde C denota una bola cian y W denota una bola blanca.

En una operación, él elige una bola cian en la fila actual. Supongamos que esta bola está en la posición $i$ en la fila actual. Entonces, todas las bolas cuyas posiciones difieren de $i$ en a lo sumo $k$ son eliminadas, incluyendo la propia bola cian elegida. Después de la eliminación, las partes izquierda y derecha restantes se concatenan.

Por ejemplo, cuando $k = 1$, una posible operación es

donde se elige la bola con el borde grueso y las bolas dentro del recuadro rojo son eliminadas.

Encuentre el número mínimo de operaciones necesarias para eliminar toda la fila. Si es imposible, informe de ello.

Entrada

Hay múltiples casos de prueba. La primera línea de la entrada contiene un único entero $T$ ($1 \le T$), que indica el número de casos de prueba.

Para cada caso de prueba, la primera línea contiene dos enteros $n$ y $k$ ($1 \le k \le n \le 10^6$). La segunda línea contiene una cadena $s$ de longitud $n$, que consiste únicamente en los caracteres C y W.

Se garantiza que la suma de $n$ en todos los casos de prueba no supera $10^6$.

Salida

Para cada caso de prueba, si es imposible eliminar toda la fila, imprima una sola línea con un único entero $-1$. De lo contrario, imprima una sola línea que contenga un único entero, indicando el número mínimo de operaciones necesarias para eliminar toda la fila.

Ejemplos

Entrada 1

3
1 1
C
5 2
WWCWW
4 1
WWWW

Salida 1

1
1
-1

Nota

En el primer caso de prueba, Little Cyan Fish elige la única bola.

En el segundo caso de prueba, él elige la bola cian central; debido a que $k = 2$, toda la fila se elimina en una sola operación.

En el tercer caso de prueba, no hay ninguna bola cian, por lo que no se puede realizar ninguna operación.