[Solution] Black and White Stripe Codeforces Solution

[Solution] Black and White Stripe Codeforces Solution

D. Black and White Stripe

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You have a stripe of checkered paper of length n$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$k$ consecutive black cells on the stripe?

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

Input

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

Solution Click Below:-  CLICK HERE

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

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

Black and White Stripe Codeforces Solution

It is guaranteed that the sum of values n$n$ does not exceed 2⋅105$2\cdot {10}^5$.

Output

For each of t$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$k$ consecutive black cells.