Little Cyan Fish는 $n$개의 공이 일렬로 놓여 있다. 각 공은 청색(cyan)이거나 흰색(white)이다. 이 줄은 길이 $n$인 문자열 $s$로 표현되며, 여기서 C는 청색 공을, W는 흰색 공을 나타낸다.

한 번의 연산에서, 그는 현재 줄에 있는 청색 공 하나를 선택한다. 이 공이 현재 줄의 $i$번째 위치에 있다고 가정하자. 그러면 선택된 청색 공을 포함하여 $i$와의 위치 차이가 최대 $k$인 모든 공이 제거된다. 제거 후, 남은 왼쪽 부분과 오른쪽 부분이 이어 붙여진다.

예를 들어, $k = 1$일 때 가능한 연산 중 하나는 다음과 같다.

굵은 테두리가 있는 공이 선택되고 빨간색 상자 안의 공들이 제거된다.

전체 줄을 제거하는 데 필요한 최소 연산 횟수를 구하라. 만약 불가능하다면, 그 사실을 보고하라.

입력

여러 개의 테스트 케이스가 존재한다. 입력의 첫 번째 줄에는 테스트 케이스의 수를 나타내는 정수 $T(1 \le T)$가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 두 정수 $n$과 $k(1 \le k \le n \le 10^6)$가 주어진다. 두 번째 줄에는 C와 W로만 구성된 길이 $n$의 문자열 $s$가 주어진다.

모든 테스트 케이스에 대한 $n$의 합은 $10^6$을 넘지 않음이 보장된다.

출력

각 테스트 케이스에 대해, 전체 줄을 제거하는 것이 불가능하다면 $-1$을 출력한다. 그렇지 않다면, 전체 줄을 제거하는 데 필요한 최소 연산 횟수를 나타내는 정수 하나를 출력한다.

예제

입력 1

3
1 1
C
5 2
WWCWW
4 1
WWWW

출력 1

1
1
-1

참고

첫 번째 예제 테스트 케이스에서, Little Cyan Fish는 유일한 공을 선택한다.

두 번째 예제 테스트 케이스에서, 그는 가운데 청색 공을 선택한다. $k = 2$이므로, 한 번의 연산으로 전체 줄이 제거된다.

세 번째 예제 테스트 케이스에서는 청색 공이 없으므로, 어떠한 연산도 수행할 수 없다.