У Маленькой Голубой Рыбки есть ряд из $n$ шаров. Каждый шар либо голубой, либо белый. Ряд описывается строкой $s$ длины $n$, где $C$ обозначает голубой шар, а $W$ — белый шар.

За одну операцию он выбирает голубой шар в текущем ряду. Предположим, что этот шар находится на позиции $i$ в текущем ряду. Тогда все шары, чьи позиции отличаются от $i$ не более чем на $k$, удаляются, включая сам выбранный голубой шар. После удаления оставшиеся левая и правая части соединяются.

Например, при $k = 1$ одна из возможных операций выглядит так:

где выбран шар с толстой границей, а шары внутри красной рамки удаляются.

Найдите минимальное количество операций, необходимых для удаления всего ряда. Если это невозможно, выведите соответствующий ответ.

Входные данные

Входные данные содержат несколько тестовых случаев. Первая строка содержит целое число $T$ ($1 \le T$), указывающее количество тестовых случаев.

Для каждого тестового случая первая строка содержит два целых числа $n$ и $k$ ($1 \le k \le n \le 10^6$). Вторая строка содержит строку $s$ длины $n$, состоящую только из символов $C$ и $W$.

Гарантируется, что сумма $n$ по всем тестовым случаям не превышает $10^6$.

Выходные данные

Для каждого тестового случая, если удалить весь ряд невозможно, выведите одну строку с числом $-1$. В противном случае выведите одну строку, содержащую минимальное количество операций, необходимых для удаления всего ряда.

Примеры

Примеры 1

3
1 1
C
5 2
WWCWW
4 1
WWWW

Выходные данные 1

1
1
-1

Примечание

В первом примере Маленькая Голубая Рыбка выбирает единственный шар.

Во втором примере он выбирает средний голубой шар; так как $k = 2$, весь ряд удаляется за одну операцию.

В третьем примере нет голубых шаров, поэтому никакую операцию выполнить нельзя.