Garden Trouble

Interview

Time limit1sMemory limit128 MB

Summary

Find the longest contiguous segment of the garden that holds at most K chestnut trees.

Level: Easy3 of 10
Topics: Sliding window, Two pointers
Solved: No attempts yet

Problem

Mr. Wincenty loves his garden dearly, but he really hates working in it, and above all he hates raking up the leaves that fall every autumn. After several years (and just as many autumns spent raking) Mr. Wincenty decided that enough was enough: his garden is simply too big. So he made up his mind to give part of his land to the neighbors (let them rake the leaves instead).

Mr. Wincenty's garden has an unusual shape. It is a rectangle of size $1 \times N$ , divided into $N$ consecutive cells of size $1 \times 1$ . Each cell holds either grass or a single chestnut tree. Mr. Wincenty wants to keep as large a part of the garden as possible, subject to the following conditions:

The kept part may contain at most $K$ chestnut trees.
The kept part must be contiguous, that is, it must form a run of consecutive cells.

What is the maximum length of the garden fragment that Mr. Wincenty can keep?

Input

The first line contains the number of tests $L$ ( $L \le 5$ ). The descriptions of the individual tests follow.

Each test consists of two lines. The first line contains the natural numbers $N$ and $K$ ( $0 < K \le N \le 1\,000\,000$ ).

The second line describes the garden as a string of length $N$ . Each character of the string is either 'K' or 'T', depending on whether the corresponding cell holds a chestnut tree ('K') or only grass ('T').

Output

For each test, print on its own line the maximum length of the garden fragment that Mr. Wincenty can keep.

Examples5

Example 1

Input

3
10 1
KTTTTTTTTK
10 3
TKTKTKTKTK
10 5
KTKTTTKKKK

Expected output

9
7
9

Example 2
Input
```
1
5 2
TTTTT
```
Expected output
```
5
```
Example 3
Input
```
1
5 2
KKKKK
```
Expected output
```
2
```
Example 4
Input
```
1
5 5
KKKKK
```
Expected output
```
5
```
Example 5
Input
```
1
1 1
K
```
Expected output
```
1
```