정원의 골칫거리

면접 대비

시간 제한1초메모리 제한128 MB

요약

밤나무가 최대 K그루까지 들어 있는 가장 긴 연속 정원 구간 길이를 구합니다.

난이도: 쉬움10점 중 3점
유형: 슬라이딩 윈도우, 투 포인터
정답자: 아직 제출이 없습니다

문제

빈센티 씨는 자기 정원을 무척 아끼지만, 정원에서 일하는 것은 정말 싫어합니다. 특히 가을마다 떨어지는 낙엽을 갈퀴로 긁어모으는 일을 몹시 싫어하죠. 몇 해 (그리고 그만큼의 낙엽 긁는 가을을) 보내고 나서, 빈센티 씨는 더는 못 참겠다고 결심했습니다. 정원이 너무 큰 것이 문제였습니다. 그래서 그는 정원의 일부를 이웃에게 넘기기로 했습니다 (낙엽은 이웃이 긁으라죠).

빈센티 씨의 정원은 생김새가 조금 특이합니다. 정원은 $1 \times N$ 크기의 직사각형이고, 가로로 이어진 $N$ 개의 $1 \times 1$ 칸으로 나뉩니다. 각 칸에는 잔디가 자라 있거나 밤나무가 한 그루 서 있습니다. 빈센티 씨는 다음 두 조건을 지키면서 정원을 최대한 넓게 남기고 싶습니다.

남기는 부분에 있는 밤나무는 최대 $K$ 그루까지만 허용됩니다.
남기는 부분은 연속이어야 합니다. 즉, 서로 붙어 있는 칸들이 이루는 하나의 구간이어야 합니다.

빈센티 씨가 남길 수 있는 정원 구간의 최대 길이는 얼마일까요?

입력

첫째 줄에 테스트의 개수 $L$ 이 주어집니다 ( $L \le 5$ ). 이어서 각 테스트의 설명이 차례로 주어집니다.

한 테스트는 두 줄로 이루어집니다. 첫째 줄에는 자연수 $N$ 과 $K$ 가 주어집니다 ( $0 < K \le N \le 1\,000\,000$ ).

둘째 줄에는 정원의 상태가 길이 $N$ 인 문자열로 주어집니다. 문자열의 각 문자는 'K' 또는 'T'이며, 해당 칸에 밤나무가 있으면 'K', 잔디만 있으면 'T'입니다.

출력

각 테스트마다 빈센티 씨가 남길 수 있는 정원 구간의 최대 길이를 한 줄에 하나씩 출력하세요.

예제5

예제 1

입력

3
10 1
KTTTTTTTTK
10 3
TKTKTKTKTK
10 5
KTKTTTKKKK

예상 출력

9
7
9

예제 2
입력
```
1
5 2
TTTTT
```
예상 출력
```
5
```
예제 3
입력
```
1
5 2
KKKKK
```
예상 출력
```
2
```
예제 4
입력
```
1
5 5
KKKKK
```
예상 출력
```
5
```
예제 5
입력
```
1
1 1
K
```
예상 출력
```
1
```