You 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.


-----Examples-----

Input
4
5 3
BBWBW
5 5
BBWBW
5 1
BBWBW
1 1
W
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'.

Difficulty: EASY
Tags: Amortized analysis

Implementation
Skill types: Amortized analysis

Starter code:

Solutions:
import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, k) = map(int, input().strip().split())
	s = input()
	a = s.count('B')
	b = n - a
	if k == 1 and a == 0:
		print(1)
	elif k == 1:
		print(0)
	elif k == n:
		print(b)
	else:
		co = s[:k].count('W')
		a = co
		for i in range(k, n):
			if s[i] == s[i - k]:
				continue
			elif s[i] == 'B':
				a -= 1
				co = min(co, a)
			else:
				a += 1
		print(co)


def main():
	for _ in range(int(input())):
		problem()

def problem():
	(n, k) = map(int, input().split())
	strip = input().rstrip()
	(i, j) = (0, k)
	window_white = strip[:k].count('W')
	answer = window_white
	while j < n:
		i += 1
		j += 1
		if strip[i - 1] == 'W':
			window_white -= 1
		if strip[j - 1] == 'W':
			window_white += 1
		if window_white < answer:
			answer = window_white
	print(answer)
import sys
input = sys.stdin.readline
exit(main())


ct = int(input())
answer = []

def resolve(s, n, k):
	l = 0
	r = k - 1
	w = 0
	for i in s[:k]:
		if i == 'W':
			w += 1
	m_w = w
	for i in range(n - k):
		l += 1
		r += 1
		if s[l - 1] == 'W':
			m_w -= 1
		if s[r] == 'W':
			m_w += 1
		if m_w < w:
			w = m_w
	return w
for i in range(ct):
	(n, k) = list(map(int, input().split()))
	s = input()
	answer.append(resolve(s, n, k))
for i in answer:
	print(i)


from sys import stdin, stdout, setrecursionlimit
import collections
import math
from collections import deque

def test():
	return

def solve():
	return

def main():
	for _ in range(int(input())):
		(n, k) = map(int, input().split())
		s = input().strip()
		d = deque(s[:k])
		m = d.count('W')
		c = d.count('W')
		for i in range(k, n):
			add = s[i]
			rem = d.popleft()
			if rem == 'W':
				c -= 1
			d.append(add)
			if add == 'W':
				c += 1
			m = min(c, m)
		print(m)
	return
input = stdin.readline
main()


from sys import stdin, stdout
import sys
from collections import defaultdict
sys.setrecursionlimit(10 ** 6)

def main():
	t = int(stdin.readline().strip())
	for tc in range(1, t + 1):
		(n, k) = map(int, stdin.readline().split())
		strip = stdin.readline().strip()
		white = 0
		minwhite = 10000000000
		for i in range(k):
			if strip[i] == 'W':
				white += 1
		minwhite = white
		i = 0
		j = k - 1
		while j + 1 < n:
			if strip[i] == 'W':
				white -= 1
			i += 1
			j += 1
			if strip[j] == 'W':
				white += 1
			minwhite = min(minwhite, white)
		print(minwhite)
main()


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	w = input()[:-1]
	s = w[:k]
	c = s.count('W')
	d = c
	for i in range(n - k):
		if w[i] == 'W':
			c -= 1
		if w[i + k] == 'W':
			c += 1
		d = min(d, c)
	print(d)


from sys import stdin
from collections import Counter
from bisect import bisect_left as bl
from collections import defaultdict
input = stdin.readline
for test in range(int(input())):
	(n, k) = map(int, input().split())
	stripe = input().strip()
	curr = s = stripe[:k].count('W')
	for i in range(k, n):
		if stripe[i] == 'B' and stripe[i - k] == 'W':
			s -= 1
		elif stripe[i] == 'W' and stripe[i - k] == 'B':
			s += 1
		curr = min(curr, s)
	print(curr)


from random import getrandbits
RANDOM = getrandbits(32)

class Wrapper(int):

	def __init__(self, x):
		int.__init__(x)

	def __hash__(self):
		return super(Wrapper, self).__hash__() ^ RANDOM
T = int(input())
q = []
for i in range(T):
	a = input().split()
	(n, k) = (int(a[0]), int(a[1]))
	data = input()
	q.append((n, k, data))

def solve(n, k, data):
	accum = []
	summ = 0
	for i in range(n):
		accum.append(summ)
		if data[i] == 'W':
			summ += 1
	accum.append(summ)
	ans = 2000000.0
	for i in range(k, n + 1):
		ans = min(ans, accum[i] - accum[i - k])
	print(ans)
for (n, k, data) in q:
	solve(n, k, data)


ans = ''
for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	s = input()
	bCount = 0
	for i in range(k):
		if s[i] == 'B':
			bCount += 1
	res = min(n, k - bCount)
	for i in range(k, n):
		if s[i - k] == 'B':
			bCount -= 1
		if s[i] == 'B':
			bCount += 1
		res = min(res, k - bCount)
	ans += str(res) + '\n'
print(ans)


def solve(b, k):
	w = 0
	bb = 0
	for i in range(k):
		if b[i] == 'W':
			w += 1
		else:
			bb += 1
	ans = w
	for i in range(k, len(b)):
		if b[i - k] == 'W':
			w -= 1
		else:
			bb -= 1
		if b[i] == 'W':
			w += 1
		else:
			bb += 1
		if w < ans:
			ans = w
	return ans
t = int(input())
for i in range(t):
	a = input().split(' ')
	n = int(a[0])
	k = int(a[1])
	b = input()
	c = solve(b, k)
	print(c)


def sol(n, k, s):
	s = list(s)
	w = 0
	for i in range(k):
		if s[i] == 'W':
			w = w + 1
	w1 = w
	for i in range(1, n - k + 1):
		if s[i - 1] == 'W':
			w1 = w1 - 1
		if s[i + k - 1] == 'W':
			w1 = w1 + 1
		if w1 < w:
			w = w1
	return w
t = int(input())
for ii in range(t):
	(n, k) = map(int, input().split())
	s = input()
	print(sol(n, k, s))


import sys
input = sys.stdin.readline
T = int(input())
for i in range(T):
	(n, k) = map(int, input().split())
	stripe = input()
	cnt = 0
	for j in range(k):
		if stripe[j] == 'W':
			cnt += 1
	mn = cnt
	for i in range(1, n - k + 1):
		if stripe[i - 1] == 'W':
			cnt -= 1
		if stripe[i + k - 1] == 'W':
			cnt += 1
		mn = min(cnt, mn)
	print(mn)


tc = int(input())
for t in range(tc):
	(n, k) = map(int, input().split())
	ar = input()
	net = ar.count('B')
	if k == 1 and net == 0:
		print(1)
	elif k == 1:
		print(0)
	elif k == n:
		print(n - net)
	else:
		net = ar[:k].count('W')
		co = net
		for i in range(k, n):
			if ar[i] != ar[i - k]:
				if ar[i] == 'W':
					net += 1
				else:
					net -= 1
					co = min(co, net)
		print(co)


def func(n, k, col):
	i = 0
	j = k
	min_len = 0
	if len(col) == 1:
		if col[0] == 'B':
			return 0
		else:
			return 1
	for elem in range(i, j):
		if col[elem] == 'W':
			min_len += 1
	cur = min_len
	while j < n:
		deleted_elem = col[i]
		new_elem = col[j]
		i += 1
		j += 1
		if deleted_elem == new_elem:
			continue
		elif deleted_elem == 'B':
			cur += 1
		elif deleted_elem == 'W':
			cur -= 1
			if cur < min_len:
				min_len = cur
	return min_len

def main():
	t = int(input())
	for i in range(t):
		s = list(map(int, input().split()))
		n = s[0]
		k = s[1]
		col = input()
		ans = func(n, k, col)
		print(ans)
main()


for t in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	f = s[:k]
	c = f.count('W')
	mini = c
	for i in range(1, n - k + 1):
		if s[i - 1] == 'W':
			c -= 1
		if s[i + k - 1] == 'W':
			c += 1
		if c < mini:
			mini = c
	print(mini)


t = int(input())
otvet = []
for i in range(t):
	s0 = input().split()
	n = int(s0[0])
	k = int(s0[1])
	s = input()
	w = ans = s[:k].count('W')
	for j in range(1, n - k + 1):
		if s[j - 1] == 'W':
			w -= 1
		if s[j + k - 1] == 'W':
			w += 1
		ans = min(ans, w)
	otvet.append(ans)
for m in range(len(otvet)):
	print(otvet[m])


for i in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	c = 0
	for j in range(k):
		if s[j] == 'W':
			c += 1
	m = c
	for j in range(k, n):
		if s[j - k] == 'W' and s[j] == 'B':
			c -= 1
			if c < m:
				m = c
		elif s[j - k] == 'B' and s[j] == 'W':
			c += 1
	print(m)


def f():
	nk = list(input().split())
	n = int(nk[0])
	k = int(nk[1])
	a = input()
	zeros_number = 0
	result = n
	for j in range(k):
		if a[j] == 'W':
			zeros_number += 1
	result = zeros_number
	for i in range(1, n - k + 1):
		zeros_number += 1 if a[i + k - 1] == 'W' else 0
		zeros_number -= 1 if a[i - 1] == 'W' else 0
		result = min(result, zeros_number)
	return result
t = input()
for i in range(int(t)):
	print(f())


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	s = input()
	wc = s[:k].count('W')
	initial = 0
	final = k - 1
	value = wc
	while final < n:
		if s[initial] == 'W':
			wc -= 1
		initial += 1
		if final + 1 < n:
			final += 1
		else:
			break
		if s[final] == 'W':
			wc += 1
		if wc < value:
			value = wc
	print(value)


x = int(input())

def cal(n, m, s):
	b = s[:m].count('B')
	w = m - b
	if w == 0:
		return 0
	res = w
	for i in range(n - m):
		if s[i] == 'W':
			w -= 1
		else:
			b -= 1
		if s[i + m] == 'W':
			w += 1
		else:
			b += 1
		res = min(res, w)
		if res == 0:
			return 0
	return res
for jj in range(x):
	(n, m) = [int(i) for i in input().split(' ')]
	s = input()
	print(cal(n, m, s))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = input()
	b = a[0:k]
	c = b.count('W')
	mn = c
	j = 0
	for i in range(k, n):
		if a[j] == 'W':
			c -= 1
		if a[i] == 'W':
			c += 1
		if c < mn:
			mn = c
		if mn == 0:
			break
		j += 1
	print(mn)


def check_str(n, k, s):
	mini = k
	count = 0
	first = 0
	i = 0
	while i < k:
		if s[i] == 'W':
			count += 1
		i += 1
	if count < mini:
		mini = count
	for i in range(k, n):
		if s[first] == 'W':
			count -= 1
		if s[i] == 'W':
			count += 1
		first += 1
		if count < mini:
			mini = count
	print(mini)

def main():
	t = int(input())
	for i in range(t):
		(n, k) = map(int, input().split())
		s = input()
		check_str(n, k, s)
main()


for i in range(int(input())):
	(a, b) = map(int, input().split())
	x = input()
	l = 0
	r = b
	v = x[:b].count('W')
	d = v
	while True:
		if r == a:
			break
		if x[l] == 'W':
			v -= 1
		if x[r] == 'W':
			v += 1
		if v < d:
			d = v
		r += 1
		l += 1
	print(d)


from collections import Counter
from functools import lru_cache
import heapq
from itertools import combinations
import math
import sys
sys.setrecursionlimit(2 * 10 ** 5 + 5)
result = []
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	string = input().rstrip()

	def solve(k):
		count = 0
		startIdx = 0
		currentMin = float('inf')
		for (endIdx, char) in enumerate(string):
			if char == 'W':
				count += 1
			if endIdx - startIdx + 1 == k:
				currentMin = min(currentMin, count)
			elif endIdx - startIdx + 1 > k:
				if string[startIdx] == 'W':
					count -= 1
				startIdx += 1
				currentMin = min(currentMin, count)
		return currentMin
	print(solve(k))


nlines = int(input())
for i in range(nlines):
	(n, k) = map(int, input().split())
	stripe = input()
	ans = k
	ans = 0
	for x in range(k):
		if stripe[x] == 'W':
			ans = ans + 1
	i = k
	curr_ans = ans
	while i < n and ans > 0:
		if stripe[i] == 'W':
			curr_ans = curr_ans + 1
		if stripe[i - k] == 'W':
			curr_ans = curr_ans - 1
		if curr_ans < ans:
			ans = curr_ans
		i = i + 1
	print(ans)


def resi():
	(n, k) = map(int, input().split())
	a = input()
	br = 0
	for i in range(k):
		if a[i] == 'W':
			br += 1
	mn = br
	for i in range(k, n):
		if a[i] == 'W':
			br += 1
		if a[i - k] == 'W':
			br -= 1
		if mn > br:
			mn = br
	print(mn)
	return
for _ in range(int(input())):
	resi()


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = [1 if x == 'B' else 0 for x in input()]
	first = sum(arr[:k])
	ans = k - first
	for i in range(k, n):
		first += arr[i]
		first -= arr[i - k]
		ans = min(ans, k - first)
	print(ans)


def solve(s, k):
	(left, right) = (0, k)
	cnt = 0
	for i in range(k):
		if s[i] == 'W':
			cnt += 1
	ans = cnt
	while right < len(s):
		if s[right] == 'W':
			cnt += 1
		if s[left] == 'W':
			cnt -= 1
		ans = min(ans, cnt)
		right += 1
		left += 1
	return ans

def main():
	t = int(input())
	for i in range(t):
		(n, k) = list(map(int, input().split()))
		s = input()
		print(solve(s, k))
main()


def exe():
	l = []
	c = s[0:k].count('W')
	l.append(c)
	for i in range(1, n - (k - 1)):
		if s[i - 1] == 'W':
			c = c - 1
		if s[i + k - 1] == 'W':
			c += 1
		l.append(c)
	return min(l)
for i in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	print(exe())


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	ans = s[0:k].count('W')
	x = ans
	for i in range(1, n - k + 1):
		if s[i - 1] == 'W':
			x -= 1
		if s[i + k - 1] == 'W':
			x += 1
		if x < ans:
			ans = x
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	m = s[:k].count('W')
	w = m
	for i in range(1, n - k + 1):
		if s[i - 1] == 'W':
			w -= 1
		if s[i + k - 1] == 'W':
			w += 1
		if w < m:
			m = w
	print(m if m >= 0 else 0)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	temp = ctr = s[:k].count('W')
	for i in range(n - k):
		if s[i] == 'W':
			ctr -= 1
		if s[i + k] == 'W':
			ctr += 1
		temp = min(ctr, temp)
	print(temp)


def fun(ans, x):
	s = 0
	for i in range(len(ans)):
		if ans[i] == 'W':
			s += 1
		ans[i] = s
	m = ans[x]
	for i in range(1, len(ans) - x):
		if m > ans[i + x] - ans[i - 1]:
			m = ans[i + x] - ans[i - 1]
	return m
n = int(input())
for _ in range(n):
	(_, n) = input().split()
	arr = input()
	arr = list(arr)
	print(fun(arr, int(n) - 1))


Tc = int(input())
for _ in range(Tc):
	(length, k) = map(int, input().split())
	stripe = input()
	ans = k
	white = 0
	for x in range(k):
		if stripe[x] == 'W':
			white = white + 1
	ans = white
	for x in range(1, length - k + 1):
		if stripe[x + k - 1] == 'W':
			white = white + 1
		if stripe[x - 1] == 'W':
			white = white - 1
		if white == 0:
			ans = white
			break
		if white < ans:
			ans = white
	print(ans)


def f():
	(n, k) = map(int, input().split())
	a = input()
	m = a[:k].count('W')
	ans = m
	for i in range(n - k):
		m -= 1 if a[i] == 'W' else 0
		m += 1 if a[i + k] == 'W' else 0
		ans = min(ans, m)
	print(ans)
for _ in range(int(input())):
	f()


t = int(input())
for tt in range(t):
	(n, k) = map(int, input().split())
	s = input()
	mins = 0
	for i in range(k):
		if s[i] == 'W':
			mins += 1
	curs = mins
	for j in range(n - k):
		if s[j] == 'W':
			curs -= 1
		if s[j + k] == 'W':
			curs += 1
		if curs < mins:
			mins = curs
	print(mins)


def BWcheck(string, k):
	count = 0
	for i in range(k):
		if string[i] != 'B':
			count += 1
	minimum = count
	sofar = count
	for i in range(k, len(string)):
		if string[i] == string[i - k]:
			continue
		elif string[i] == 'B' and string[i - k] == 'W':
			sofar -= 1
			minimum = min(minimum, sofar)
		elif string[i] == 'W' and string[i - k] == 'B':
			sofar += 1
	return minimum
n = int(input())
for i in range(n):
	k = int(input().split(' ')[1])
	string = input()
	print(BWcheck(string, k))


def solve():
	(n, k) = map(int, input().split())
	s = input()
	res = s[:k].count('W')
	curr = res
	for i in range(n - k):
		if s[i + k] == 'W':
			curr += 1
		if s[i] == 'W':
			curr -= 1
		res = min(res, curr)
	return res

def main():
	for _ in range(int(input())):
		print(solve())
	return
main()


t = int(input())
for j in range(t):
	(n, k) = map(int, input().split())
	s = input()
	sm = 'B' * k
	numbl = 0
	for i in range(k):
		if s[i] == 'B':
			numbl += 1
	maxnumbl = numbl
	q = k
	while maxnumbl < k and q < n:
		if s[q - k] == 'B':
			numbl -= 1
		if s[q] == 'B':
			numbl += 1
		if numbl > maxnumbl:
			maxnumbl = numbl
		q += 1
	print(k - maxnumbl)


for _ in range(int(input())):
	(n, k) = map(int, input().split(' '))
	s = input()
	w = 0
	for i in range(k):
		if s[i] == 'W':
			w += 1
	if w == 0:
		print(0)
		continue
	wt = w
	for i in range(1, n - k + 1):
		if s[i - 1] == 'W':
			wt -= 1
		if s[i + k - 1] == 'W':
			wt += 1
		if wt < w:
			w = wt
	print(w)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	a = sum([s[i] == 'B' for i in range(k)])
	if a == k:
		print(0)
	else:
		b = int(a)
		for i in range(k, n):
			a = a + (s[i] == 'B') - (s[i - k] == 'B')
			if a > b:
				b = int(a)
		print(k - b)


asdasf = int(input())
for test in range(asdasf):
	(n, k) = map(int, input().split())
	s = input()
	c = f = 0
	for i in range(k):
		if s[i] == 'W':
			c += 1
	f = c
	for i in range(k, n):
		if s[i] == 'W':
			c = c + 1
		if s[i - k] == 'W':
			c = c - 1
		if c < f:
			f = c
	print(f)


def solve():
	(n, k) = map(int, input().split())
	s = input()
	s2 = s[0:k]
	prev = 0
	countW = s2.count('W')
	ans = countW
	for i in range(1, len(s) - k + 1):
		if s[prev] == 'W' and s[i + k - 1] == 'B':
			countW -= 1
		elif s[prev] == 'B' and s[i + k - 1] == 'W':
			countW += 1
		prev += 1
		ans = min(ans, countW)
	print(ans)
	return
for i in range(int(input())):
	solve()


t = int(input())
for j in range(t):
	(n, k) = input().split()
	n = int(n)
	k = int(k)
	p = input()
	numb = 0
	numw = 0
	for i in range(0, k):
		if p[i] == 'B':
			numb += 1
		else:
			numw += 1
	if numb >= k:
		print(0)
		continue
	ans = numw
	for i in range(k, n):
		if p[i - k] == 'B':
			numb -= 1
		else:
			numw -= 1
		if p[i] == 'B':
			numb += 1
		else:
			numw += 1
		ans = min(ans, numw)
	print(ans)


for _ in range(int(input())):
	a = input().split()
	(n, k) = (int(a[0]), int(a[1]))
	x = input()
	mini = 10 ** 18
	mini = min(x[:k].count('W'), mini)
	curr = mini
	for i in range(k, len(x)):
		if x[i] == 'W':
			curr += 1
		if x[i - k] == 'W':
			curr -= 1
		mini = min(mini, curr)
	print(mini)


import sys
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	if n == k:
		print(s.count('W'))
	else:
		j = 0
		x = s[0:k].count('W')
		mini = x
		for i in range(k, len(s)):
			if s[i] == 'W' and s[j] == 'B':
				x += 1
				mini = min(mini, x)
				j = j + 1
			elif s[i] == 'B' and s[j] == 'W':
				x -= 1
				mini = min(mini, x)
				j = j + 1
			else:
				j = j + 1
		print(mini)


def solve(n, k):
	s = input()
	c = 0
	m = 200001
	for i in range(k):
		if s[i] == 'W':
			c += 1
	m = min(m, c)
	for i in range(0, n - k):
		if s[i] == 'W':
			c -= 1
		if s[k + i] == 'W':
			c += 1
		m = min(m, c)
	print(m)
t = int(input())
for i in range(t):
	(n, k) = [int(x) for x in input().split(' ')]
	solve(n, k)


t = int(input())
while t:
	(n, k) = list(map(int, input().split()))
	s = input()
	curr_answ = s[:k].count('W')
	answ = curr_answ
	for i in range(k, n):
		if s[i - k] == 'W':
			curr_answ -= 1
		if s[i] == 'W':
			curr_answ += 1
		answ = min(answ, curr_answ)
	print(max(answ, 0))
	t -= 1


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	cnt = s[:k].count('W')
	mn = cnt
	for i in range(k, n):
		cnt += (s[i] == 'W') - (s[i - k] == 'W')
		mn = min(mn, cnt)
	print(mn)


t = int(input())
for i in range(t):
	(n, k) = list(map(int, input().split()))
	s = list(input())
	len = s[0:k].count('B')
	tmp = len
	for i in range(1, n - k + 1):
		if s[i - 1] != s[i + k - 1]:
			if s[i + k - 1] == 'B':
				tmp += 1
			else:
				tmp -= 1
		if tmp > len:
			len = tmp
		if len == k:
			break
	print(k - len)


for _ in [0] * int(input()):
	(n, k) = map(int, input().split())
	s = input()
	a = s[:k].count('W')
	mini = a
	for i in range(1, n - k + 1):
		a += (s[k + i - 1] == 'W') - (s[i - 1] == 'W')
		mini = min(mini, a)
	print(mini)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	max_sum = 0
	for i in range(k):
		if s[i] == 'B':
			max_sum += 1
	temp_sum = max_sum
	for i in range(1, len(s) - k + 1):
		if s[i - 1] == 'B':
			temp_sum -= 1
		if s[i + k - 1] == 'B':
			temp_sum += 1
		if temp_sum > max_sum:
			max_sum = temp_sum
	answer = k - max_sum
	if answer < 0:
		print(0)
	else:
		print(answer)


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	arr = input()
	count = 0
	for i in arr[:k]:
		if i == 'W':
			count += 1
	if count == 0:
		print(0)
		continue
	result = count
	for i in range(k, n):
		if arr[i] == 'W':
			count += 1
		if arr[i - k] == 'W':
			count -= 1
		if result > count:
			result = count
	print(result)


def solve():
	(n, k) = map(int, input().split())
	cells = input()
	color = 0
	min_col = 0
	for i in range(k):
		if cells[i] == 'W':
			color += 1
			min_col += 1
	for i in range(k, n):
		idx_before = i - k
		idx_now = i
		if cells[idx_before] == 'W':
			color -= 1
		if cells[idx_now] == 'W':
			color += 1
		min_col = min(min_col, color)
	return min_col
tt = int(input())
for _ in range(tt):
	print(solve())


import math
t = int(input())
char_to = {'B': 0, 'W': 1}
for i in range(t):
	(n, m) = list(map(int, input().split()))
	text = input()
	win = text[:m]
	count = win.count('W')
	counter = [count]
	if m == 1:
		if text.count('B') > 0:
			print(0)
		else:
			print(1)
		continue
	for i in range(m, n):
		count += char_to[text[i]] - char_to[text[i - m]]
		counter.append(count)
	print(min(counter))


n = int(input())
while n > 0:
	(tam, k) = input().split()
	s = input()
	tam = int(tam)
	k = int(k)
	w = 0
	i = 0
	while i < k:
		if s[i] == 'W':
			w += 1
		i += 1
	menor = w
	j = 0
	while w != 0 and i < tam:
		if s[i] != s[j]:
			if s[i] == 'W':
				w += 1
			else:
				w -= 1
				if menor > w:
					menor = w
		i += 1
		j += 1
	print(menor)
	n -= 1


cases = int(input())
for i in range(cases):
	strNsubStrSize = list(map(int, input().split()))
	str = input()
	min = str[:strNsubStrSize[1]].count('W')
	w = min
	for i in range(1, strNsubStrSize[0] - strNsubStrSize[1] + 1):
		if str[i - 1] == 'W':
			w -= 1
		if str[i + strNsubStrSize[1] - 1] == 'W':
			w += 1
		if w < min:
			min = w
	print(min)


import sys
input = sys.stdin.readline

def solve():
	(n, k) = map(int, input().split())
	s = input()
	ans = float('inf')
	pr = [0] * (n + 1)
	if s[0] == 'W':
		pr[0] = 1
	for i in range(1, n + 1):
		pr[i] = pr[i - 1] + int(s[i - 1] == 'W')
	for i in range(k, n + 1):
		ans = min(ans, pr[i] - pr[i - k])
	print(ans)
for _ in range(int(input())):
	solve()


for _ in range(int(input())):
	(a, b) = input().split()
	a = int(a)
	b = int(b)
	s = list(input())
	k = 0
	x = s[:b]
	k = x.count('B')
	km = k
	for i in range(0, a - b):
		if s[b + i] == s[i]:
			continue
		elif s[b + i] == 'B' and s[i] == 'W':
			k += 1
			km = max(k, km)
		else:
			k -= 1
	print(b - km)


import sys
import sys, threading
from heapq import heapify, heappop, heappush
from math import log10, floor, pow, gcd, sqrt, inf, log2, ceil
from collections import defaultdict, deque, Counter
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())

def main():
	tests = inp()
	for _ in range(tests):
		(length, k) = inlt()
		board = insr()
		left = 0
		right = 0
		convert = inf
		whiteCount = 0
		while right < length:
			while right < length and right - left < k:
				whiteCount += 1 if board[right] == 'W' else 0
				right += 1
			if left < right and right - left == k:
				convert = min(convert, whiteCount)
				whiteCount -= 1 if board[left] == 'W' else 0
				left += 1
		print(convert)
main()


def runCase():
	(n, k) = map(int, input().split())
	paper = input()
	blacks = 0
	for i in range(k):
		if paper[i] == 'B':
			blacks += 1
	left = 1
	right = k
	maxBlacks = blacks
	while right < n:
		if paper[right] == 'B':
			blacks += 1
		if paper[left - 1] == 'B':
			blacks -= 1
		right += 1
		left += 1
		maxBlacks = max(maxBlacks, blacks)
	print(k - maxBlacks)
tests = int(input())
for _ in range(tests):
	runCase()


t = int(input())
for i in range(t):
	first = input().split(' ')
	n = int(first[0])
	k = int(first[1])
	p = input()
	smallest = 0
	curr = 0
	for j in range(k):
		if p[j] == 'W':
			smallest += 1
	curr = smallest
	for j in range(1, n - k + 1):
		curr = curr + (p[j + k - 1] == 'W') - (p[j - 1] == 'W')
		if curr < smallest:
			smallest = curr
	print(smallest)


t = int(input())
answers = []
for _ in range(t):
	(n, k) = [int(x) for x in str(input()).split()]
	bw_string = input()
	prefix_sum = [0]
	for chr in bw_string:
		value = 0 if chr == 'B' else 1
		prefix_sum.append(prefix_sum[-1] + value)
	min_sum = n + 1
	for j in range(0, n - k + 1):
		min_sum = min(min_sum, prefix_sum[j + k] - prefix_sum[j])
	answers.append(min_sum)
for ans in answers:
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input().strip()
	c = s[:k].count('W')
	m = c
	for i in range(k, n):
		c += (s[i] == 'W') - (s[i - k] == 'W')
		m = min(m, c)
	print(m)


t = int(input())
for p in range(t):
	(n, k) = map(int, input().split())
	s = input()
	c = 0
	for i in range(k):
		if s[i] == 'W':
			c += 1
	i = 0
	new_c = c
	while i < n - k and c != 0:
		if s[i] == 'W' and s[i + k] == 'B':
			new_c -= 1
		elif s[i] == 'B' and s[i + k] == 'W':
			new_c += 1
		c = min(c, new_c)
		i += 1
	print(c)


from posixpath import split
t = int(input())
for _ in range(t):
	(n, k) = list(map(int, input().split()))
	a = input()
	p = a[0:k]
	no = 0
	for i in p:
		if i == 'B':
			no += 1
	temp = no
	for i in range(k, n):
		if a[i - k] == 'B':
			no -= 1
		if a[i] == 'B':
			no += 1
		temp = max(temp, no)
	print(k - temp)


from itertools import accumulate
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	accumulation = tuple(accumulate(input(), lambda a, b: a + (b == 'W'), initial=0))
	print(min((accumulation[j + k] - accumulation[j] for j in range(n - k + 1))))


def fun(n, k, s):
	cnt = 0
	for i in range(k):
		if s[i] == 'W':
			cnt += 1
	L = [cnt]
	for i in range(1, n - k + 1):
		if s[i - 1] == 'W':
			cnt -= 1
		if s[i + k - 1] == 'W':
			cnt += 1
		L.append(cnt)
	return min(L)
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	cnt = fun(n, k, s)
	print(cnt)


def solve():
	l = list(map(int, input().split()))
	s = input()
	n = l[0]
	k = l[1]
	i = 0
	j = k - 1
	m = s[i:j + 1].count('W')
	i += 1
	j += 1
	c = m
	while i < n and j < n:
		if s[i - 1] == 'W':
			c -= 1
		if s[j] == 'W':
			c += 1
		m = min(c, m)
		i += 1
		j += 1
	print(m)
t = int(input())
while t > 0:
	solve()
	t -= 1


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	c = 100000000
	d = 0
	for i in range(k):
		if s[i] == 'W':
			d += 1
	c = min(c, d)
	for i in range(k, n):
		if s[i - k] == 'W':
			d -= 1
		if s[i] == 'W':
			d += 1
		c = min(c, d)
	print(c)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	prev = min(s[:k].count('W'), 10 ** 18)
	curr = prev
	for i in range(k, n):
		if s[i] == 'W':
			curr += 1
		if s[i - k] == 'W':
			curr -= 1
		prev = min(prev, curr)
	print(prev)


T = int(input())
for _ in range(T):
	(n, k) = map(int, input().split())
	s = input()
	l = 0
	r = l + k
	c = [s[l:r].count('W')]
	t = c[0]
	f = 1
	while r < n:
		if t == 0:
			print(0)
			f = 0
			break
		if s[l] == 'W':
			t -= 1
		if s[r] == 'W':
			t += 1
		l += 1
		r += 1
		c.append(t)
	c.append(t)
	if f:
		print(min(c))


for __ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	c = 0
	ans = 0
	for i in range(k):
		if s[i] == 'W':
			c = c + 1
	ans = c
	for i in range(k, n):
		if s[i] == 'W':
			c = c + 1
		if s[i - k] == 'W':
			c = c - 1
		if ans > c:
			ans = c
	print(ans)


import sys

def func():
	(n, k) = map(int, input().split())
	s = input('')
	ans = 0
	for i in range(k):
		if s[i] == 'W':
			ans += 1
	j = i
	i = 0
	c = ans
	while j != len(s) - 1:
		j += 1
		if s[j] == 'W':
			c += 1
		if s[i] == 'W':
			c -= 1
		i += 1
		ans = min(c, ans)
	print(ans)
t = int(input())
for _ in range(t):
	func()


for j in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	s = input()
	min_white = s[0:k].count('W')
	count_white = min_white
	count_black = k - count_white
	cool = 0
	for i in range(n - k):
		if s[i + k] == 'W':
			count_white += 1
		else:
			count_black += 1
		if s[i] == 'W':
			count_white -= 1
		else:
			count_black -= 1
		if count_white < min_white:
			min_white = count_white
		if count_black == k:
			print('0')
			cool = 1
			break
	if cool == 0:
		print(min_white)


def minNumber(strip, n, k):
	replace = 0
	count = 0
	index = 0
	wObject = {}
	for i in strip:
		if i == 'W':
			replace += 1
			wObject[index] = True
		else:
			wObject[index] = False
		if index - k >= 0 and wObject[index - k]:
			replace -= 1
		if index >= k:
			if count > replace:
				count = replace
		else:
			count = replace
		index += 1
	print(count)
t = int(input())
for i in range(t):
	(n, k) = list(map(int, input().split()))
	strip = input()
	minNumber(strip, n, k)


for i in range(int(input())):
	(n, m) = map(int, input().split())
	s = input()
	(l, r) = (0, m - 1)
	w_count = s[:m].count('W')
	B_count = s[:m].count('B')
	min_w = w_count
	(l, r) = (1, m)
	flag = False
	while r < n:
		if min_w == 0:
			print(0)
			flag = True
			break
		if s[l - 1] == 'W':
			w_count -= 1
		if s[r] == 'W':
			w_count += 1
		min_w = min(min_w, w_count)
		l += 1
		r += 1
	if flag == False:
		print(min_w)


for _ in range(int(input())):
	(n, k) = tuple(map(int, input().split()))
	string = list(input())
	if n == 1:
		if string[0] == 'B':
			print(0)
		else:
			print(1)
	elif string.count('B') == 0:
		print(k)
	elif string.count('B') == 1:
		print(k - 1)
	else:
		mini = k
		Wcount = 0
		for i in range(0, n):
			if string[i] == 'W':
				Wcount += 1
			if i >= k - 1:
				if mini > Wcount:
					mini = Wcount
				if string[i - k + 1] == 'W':
					Wcount -= 1
		print(mini)


t = int(input())
n = []
k = []
line = []
for i in range(t):
	nn = kk = linee = 0
	(nn, kk) = map(int, input().split())
	n.append(nn)
	k.append(kk)
	linee = input()
	line.append(linee)
for j in range(t):
	answer = line[j][0:k[j]].count('W')
	curr = answer
	i = k[j]
	while i < n[j]:
		if line[j][i - k[j]] == 'W':
			curr -= 1
		if line[j][i] == 'W':
			curr += 1
		answer = min(answer, curr)
		i += 1
	print(answer)


t = int(input())
for i in range(t):
	(n, m) = input().split()
	n = int(n)
	m = int(m)
	a = input()
	u = 1
	v = m
	mini = 0
	pt = 0
	for j in a[:m]:
		if j == 'W':
			mini += 1
	pt = mini
	pre = a[m - 1]
	for j in range(m, n):
		if a[u - 1] == 'W' and a[j] == 'B':
			pt = pt - 1
		elif a[u - 1] == 'B' and a[j] == 'W':
			pt = pt + 1
		if pt < mini:
			mini = pt
		u += 1
		pre = a[j]
	print(mini)


for time in range(int(input())):
	(n, k) = map(int, input().split())
	colors = input()
	s = 0
	for j in range(k):
		if colors[j] == 'W':
			s += 1
	mini = s
	for j in range(n - k):
		if colors[j] == 'W':
			s -= 1
		if colors[j + k] == 'W':
			s += 1
		mini = min(mini, s)
	print(mini)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	kb = sum([s[i] == 'B' for i in range(k)])
	z = kb
	for i in range(k, n):
		z += (s[i] == 'B') - (s[i - k] == 'B')
		kb = max(z, kb)
	print(k - kb)


num_of_cases = int(input())
for _ in range(num_of_cases):
	(_, target) = [int(x) for x in input().split(' ')]
	stripes = input()
	count = {'B': 0, 'W': 0}
	for stripe in stripes[:target]:
		count[stripe] += 1
	res = target
	has_found = False
	for idx in range(target, len(stripes)):
		res = min(res, count['W'])
		if res == 0:
			has_found = True
			print(0)
			break
		else:
			count[stripes[idx]] += 1
			count[stripes[idx - target]] -= 1
	if not has_found:
		print(min(res, count['W']))


import sys
input = sys.stdin.readline
T = int(input())
for _ in range(T):
	(N, K) = map(int, input().split())
	stripe = input().strip()
	(l, r) = (0, K - 1)
	ans = 0
	for i in range(K):
		if stripe[i] == 'W':
			ans += 1
	tmp_ans = ans
	while True:
		l += 1
		r += 1
		if r >= N:
			break
		if stripe[l - 1] == 'W':
			tmp_ans -= 1
		if stripe[r] == 'W':
			tmp_ans += 1
		ans = min(tmp_ans, ans)
	print(ans)


def main():
	t = int(input())
	for i in range(t):
		(n, k) = [int(i) for i in input().split(' ')]
		string = input()
		print(str(Solution(n, k, string)))

def Solution(n, k, string):
	whites = 0
	minimum = 0
	for i in range(k):
		if string[i] == 'W':
			whites += 1
	if whites == 0:
		return 0
	minimum = whites
	for i in range(k, n):
		if string[i] == 'W':
			whites += 1
		if string[i - k] == 'W':
			whites -= 1
		if whites == 0:
			return 0
		minimum = min(minimum, whites)
	return minimum
main()


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	boo = s[:k].count('W')
	var = boo
	for i in range(1, n - k + 1):
		if s[i - 1] == 'W':
			var -= 1
		if s[i + k - 1] == 'W':
			var += 1
		if var < boo:
			boo = var
	print(boo if boo >= 0 else 0)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = list((0 if char == 'B' else 1 for char in input()))
	ans = sum(s[:k])
	current = ans
	for i in range(k, n):
		current -= s[i - k]
		current += s[i]
		ans = min(ans, current)
	print(ans)


t = int(input())
for i in range(0, t):
	(n, k) = map(int, input().split())
	str1 = str(input())
	if n == k:
		count = 0
		for i in range(0, n):
			if str1[i] == 'W':
				count += 1
		print(count)
	else:
		white = 0
		for i in range(0, k):
			if str1[i] == 'W':
				white += 1
		min1 = white
		if white == 0:
			print(0)
		else:
			for i in range(k, n):
				if str1[i] == 'W':
					white += 1
				if str1[i - k] == 'W':
					white -= 1
				min1 = min(white, min1)
			print(min1)


for _ in range(0, int(input())):
	(n, k) = map(int, input().split())
	v = input()
	c = sum([x == 'W' for x in v[:k]])
	m = c
	for i in range(k, n):
		c += (v[i] == 'W') - (v[i - k] == 'W')
		m = min(m, c)
	print(m)


def solve():
	(n, k) = map(int, input().split())
	s = input()
	black = 0
	for i in range(k):
		if s[i] == 'B':
			black += 1
	maxb = black
	for i in range(1, n - k + 1):
		if s[i - 1] == 'B':
			black -= 1
		if s[i + k - 1] == 'B':
			black += 1
		maxb = max(maxb, black)
	print(k - maxb)
t = int(input())
while t != 0:
	solve()
	t -= 1


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	s = input()
	wc = s[:k].count('W')
	mini = wc
	for j in range(1, n - k + 1):
		if s[j - 1] == 'W':
			wc -= 1
		if s[j + k - 1] == 'W':
			wc += 1
		mini = min(mini, wc)
	print(mini)


def res(n, s, k):
	w = 0
	for i in range(k):
		if s[i] == 'W':
			w += 1
	b = k - w
	_min = w
	for i in range(k, n):
		if s[i] == 'B':
			b += 1
		else:
			w += 1
		if s[i - k] == 'B':
			b -= 1
		else:
			w -= 1
		_min = min(_min, w)
	return _min
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	print(res(n, s, k))