Codeforces Round 797 (Div. 3) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

implementation

two pointers

*1000

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. Black and White Stripe

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou have a stripe of checkered paper of length $$$n$$$. Each cell is either white or black.

What is the minimum number of cells that must be recolored from white to black in order to have a segment of $$$k$$$ consecutive black cells on the stripe?

If the input data is such that a segment of $$$k$$$ consecutive black cells already exists, then print 0.

Input

The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

Next, descriptions of $$$t$$$ test cases follow.

The first line of the input contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 2\cdot10^5$$$). The second line consists of the letters 'W' (white) and 'B' (black). The line length is $$$n$$$.

It is guaranteed that the sum of values $$$n$$$ does not exceed $$$2\cdot10^5$$$.

Output

For each of $$$t$$$ test cases print an integer — the minimum number of cells that need to be repainted from white to black in order to have a segment of $$$k$$$ consecutive black cells.

Example

Input

45 3BBWBW5 5BBWBW5 1BBWBW1 1W

Output

1 2 0 1

Note

In the first test case, $$$s$$$="BBWBW" and $$$k=3$$$. It is enough to recolor $$$s_3$$$ and get $$$s$$$="BBBBW". This string contains a segment of length $$$k=3$$$ consisting of the letters 'B'.

In the second test case of the example $$$s$$$="BBWBW" and $$$k=5$$$. It is enough to recolor $$$s_3$$$ and $$$s_5$$$ and get $$$s$$$="BBBBB". This string contains a segment of length $$$k=5$$$ consisting of the letters 'B'.

In the third test case of the example $$$s$$$="BBWBW" and $$$k=1$$$. The string $$$s$$$ already contains a segment of length $$$k=1$$$ consisting of the letters 'B'.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/28/2024 19:58:26 (l3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|